CS301 Solved Current Papers Fall 2021 by Adil Alvi

CS301 CURRENT PAPERS FALL 2021

Q1. What is Hash function?

A hash function is any function that can be used to map data of arbitrary size to fixed-size values.

Q2. What is Symbol table?

A symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier (or symbol) in a program's source code is associated with information relating to its declaration or appearance in the source.

Q3. How does heap sort work?

Heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

Q4. Write two application of hashing?

1. Message Digest, 2) Password Verification.

Q5. Write Pseudo Code of the Maze Generation?

Makemaze(int size) { Entrance = 0; exit = size-1; While (find(entrance) != find(exit)) { Cell1 = randomly chosen cell Cell2 = randomly chosen adjacent cell If (find(cell1) != find(cell2) { Knock down wall between cells Union(cell1, cell2)

6) What is meant by abstract data type (ADT), write its properties

An abstract data type (ADT) is a mathematical model for data types.

Properties of Abstract Data Types:

The data structure can only be accessed with defined operations. This set of operations is called interface and is exported by the entity. An entity with the properties just described is called an abstract data type (ADT).

Q7. What is collision write two methods of collision?

When two values hash to the same array location, this is called a collision there are a number of collision resolution techniques, but the most popular are chaining and open addressing.

Q8. How is traversing of nodes done in a threaded binary tree?

In order traversal of a Binary tree can either be done using recursion or with the use of an auxiliary stack. A binary tree is made threaded by making all right child pointers that would normally be NULL point to the in order successor of the node (if it exists).

Q9. Write Steps of insertion sort?

1. If it is the first element, it is already sorted. 2) Pick the next element. 3) Compare with all the elements in sorted sub-list. 4) Shift all the elements in sorted sub-list that is greater than the value to be sorted. 5) Insert the value. 6) Repeat until list is sorted.

Q10. What is the use of collision in hashing?

A collision occurs when more than one value to be hashed by a particular hash function hash to the same slot in the table or data structure (hash table) being generated by the hash function.

Q11. Write Skip list characteristics?

The skip list is a probabilistic data structure that is built upon the general idea of a linked list. The skip list uses probability to build subsequent layers of linked lists upon an original linked list. Each additional layer of links contains fewer elements, but no new elements.

Q12. Write two conditions of first deletion in avl tree?

Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).

1. Left Rotation, 2) Right Rotation

Q13. How we can generate a maze with the help of union?

Using disjoint-set we can generate a maze

• Randomly remove walls until the entrance and exit cells are in the same set.
• Removal of the wall is the same as doing a union operation.
• Do not remove a randomly chosen wall if the cells it separates are already in the same set.

Q14. 4 inclusion criteria of pixel?

1. Fraction Mode (Area Weighting), 2) Binary Mode (>50% inclusion)
2. Binary Mode (100% inclusion), 4) Compatibility Mode (Versions <3.6)

Q15. What is Dummy node?

A dummy node at the front/end of the list that is there only to reduce the need for special-case code in the linked-list operations. It is an empty template to build new nodes later.

Q16. Define heap, minimum heap and maximum heap?

A heap is a tree-based data structure that allows access to the minimum and maximum element in the tree in constant time. A min-heap is used to access the minimum element in the heap whereas the Max-heap is used when accessing the maximum element in the heap.

Q17. What is Purpose of Huffman coding?

Huffman coding is a lossless data compression algorithm. Huffman coding provides an efficient, unambiguous code by analyzing the frequencies that certain symbols appear in a message. Symbols that appear more often will be encoded as a shorter-bit string while symbols that aren't used as much will be encoded as longer strings.

Q18. What is Quad node?

Fast and easy Quad Tree implementation for node. Quad trees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions

Q19. Draw Single Right Rotation diagram?

Q20. How threaded binary tree make it possible not to use stack and recursion in traverses?

The idea of threaded binary trees is to make in order traversal faster and do it without stack and without recursion. A binary tree is made threaded by making all right child pointers that would normally be NULL point to the in order successor of the node (if it exists).

Q21. Write steps of Bubble sort?

The steps in the bubble sort can be described as below

• Exchange neighboring items until the largest item reaches the end of the array
• Repeat the above step for the rest of the array

Q22. What is Equivalence relation in data structure?

An equivalence relation allows one to partition a set of objects into equivalence classes: that is, a collection of subsets where all entries in a given equivalence class are related to all other elements within the same equivalence class.

23) Write Operation of table ADT

1. Insert, 2) find, 3) remove

Q24. How implementation of disjoint set is better than Boolean matrix?

It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation allows to find out efficiently if any two elements are in the same or different sets.