CSE2135 - Data Structure¶

Sorting, Searching, and Hashing¶

Q1(d) [1+3]: Write linear search algorithm.
Q3(a) [4]: What are the correct intermediate steps of the following data set when it is being sorted with the bubble sort? Data set: 15, 55, 35, 05, 45.
Q4(c) [5]: Write the Quick Sort algorithm.
Q5(a) [5]: Perform the Radix sort on the following array: [1256 5897 4523 1536 3246 6742 5566].
Q5(b) [3]: Suppose an array is: [6 8 1 4 5 3 7 2] and your goal is to put it into ascending order using Selection sort.
Q5(c) [6]: Let DATA be the following elements: 30, 33, 11, 22, 60, 55, 40, 44, 99, 88, 80, 77, 66. Apply the binary search algorithm to search DATA ITEM = 40 and ITEM = 85.

Q1(d) [4]: Write Linear Search algorithm and find out the complexity of it.
Q2(d) [4]: What are the correct intermediate steps of the following data set when it is being sorted with the bubble sort? Data set: 20, 60, 50, 10, 40, 70, 30.
Q3(a) [1+3]: Write the Binary Search algorithm. What is the limitation of Binary Search algorithm?
Q4(c) [5]: Write the Quick Sort algorithm.
Q7(b) [3]: Perform the Radix sort on the following array: [345 456 123 678 657 982 281 342 765 906].
Q7(c) [4]: Draw the sorting procedure of the following data for the insertion sort: 4, 3, 2, 10, 12, 1, 5, 6.
Q7(d) [1+3]: What is merge sort? Draw the diagram that shows the complete merge sort process for the following unsorted data: 38, 27, 43, 3, 9, 82, 10.

Q1(d) [3+1]: Write the Binary Search algorithm. What is the limitation of Binary Search algorithm?
Q2(a) [3]: Consider the following array and apply the Bucket sort algorithm to sort the data. A: 3216, 1953, 7269, 6517, 5432, 2806, 4920.
Q2(b) [4]: Write an algorithm for Selection sort.
Q2(c) [4]: Suppose an array is: [6 8 1 4 5 3 7 2] and your goal is to put it into ascending order using Insertion sort algorithm.
Q4(d) [4]: Write the Quick sort algorithm.
Q7(b) [1+4]: Define sorting. Consider the following array and apply the Bubble sort algorithm to sort the data. A: 77, 33, 44, 11, 22, 55, 66, 10.

Q4(a) [3]: Write down binary search algorithm.
Q4(b) [4]: Using the bubble sort algorithm, find the number C of comparisons and the number D of interchanges which alphabetize the n=6 letters in PEOPLE.
Q4(c) [2+5]: Why Quick sort is preferred over Merge sort for sorting arrays? Perform a partitioning of the array [E, V, E, R, Y, E, Q, U, A, L, K, E, Y, S, T, O, P, S, I, T] with standard quick sort partitioning (taking the E at the left as the partitioning item and listen every swapping performed in this partitioning).
Q6(c) [5]: Consider a company each of whose 68 employees is assigned a unique 4 digit employee number as follows: 9614, 5882, 6713, 4409, 1825. Find a 2 digit hash address of each number using (i) The division method. (ii) The mid square method. (iii) The folding method without reversing and with reversing.
Q7(a) [1+6]: What is meant by perfect hash function? Suppose you are given the following set of case to insert into a hash table that holds exactly seven values 113, 117, 97, 100, 114, 99. Systematically show the contents of the hash table after all the keys have been inserted sequentially using "plus 3" probing. Also determine the load factor of the resultant hash table.
Q7(b) [2+5]: What does it mean that a shorting algorithm is stable? "Radix sort can be slower and more memory hungry than some other algorithms" - Do you agree or not justify your answer.

Q2(c) [3]: Explain hashing and linear probing with suitable example.
Q7(b) [2x2]: Explain the following sorting methods: (i) Selection sort; (ii) Merge sort.