Fall 2013 CSE310 Midterm 2C (in class)Instructions:• There are six problems in this paper. Please use the space provided (below the ques-tions) to write the answers.• Budget your time to solve various problems (roughly 15 minutes for each problem) andavoid spending too much time on a particular question.• This is a closed book examination. You may not consult your books/notes. Cellphones and computers are not allowed. However, you can use a basic calculator.• You are NOT supposed to use a pencil. If you use a pencil, you cannot challenge yourgrade after the midterm is graded.NAMEASUIDQuestion ScoreP1P2P3P4P5P6Total0Problem 1C. (10 points: 2 + 2 + 2 + 2 + 2)Array A contains 10 elements from index 1 to index 10 as shown in the following.i 1 2 3 4 5 6 7 8 9 10A[i] 1 3 5 7 9 11 13 15 17 19Suppose you are applying the linear time buildheap algorithm to build a max-heap fromthe 10 elements of array A. For i = 5, 4, 3, 2, 1, show the array structure after the call tomax-heapify(A, i) is completed, using the table provided below.• After max-heapify(A, 5), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 1 3 5 7 19 11 13 15 17 9• After max-heapify(A, 4), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 1 3 5 17 19 11 13 15 7 9• After max-heapify(A, 3), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 1 3 13 17 19 11 5 15 7 9• After max-heapify(A, 2), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 1 19 13 17 9 11 5 15 7 3• After max-heapify(A, 1), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 19 17 13 15 9 11 5 1 7 31Problem 2C. (10 points: 2 + 2 + 2 + 2 + 2)Array B contains 10 elements from index 1 to index 10 as shown in the following.i 1 2 3 4 5 6 7 8 9 10B[i] 19 17 15 13 11 9 7 5 3 1Suppose you are inserting these 10 elements (in the given order) into an originally emptymin-heap, implemented in array A. For i = 6, 7, 8, 9, 10, show the array structure after thefirst i elements are inserted into the min-heap, using the table provided below.• After inserting the first 6 elements, the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 9 13 11 19 15 17• After inserting the first 7 elements, the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 7 13 9 19 15 17 11• After inserting the first 8 elements, the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 5 7 9 13 15 17 11 19• After inserting the first 9 elements, the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 3 5 9 7 15 17 11 19 13• After inserting the first 10 elements, the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 1 3 9 7 5 17 11 19 13 152Problem 3C. (20 points: 5 + 5 + 5 + 5)In class, we have studied the linear time selection algorithm with group size 5. Suppose wewill use group size 21, instead of 5. Again, we are using the median of medians as the pivotelement. Assume that there are n elements, and all elements are distinct.(5pts) What is the maximum number of elements that can appear on either side of the pivotelement? You should not use the asymptotic notations.Answer:31n42+ 22.(5pts) Let T21(n) denote the worst-case time complexity of your algorithm. Write down therecurrence formula for T21(n).Answer: T21(n) = T21(n21) + T21(31n42+ 22) + bn.(5pts) Use the asymptotic notations to denote T21(n) as a function of n.Answer: T21(n) = O(n).(5pts) Suppose you modify the original quicksort algorithm, by using the median (computedby the linear time selection algorithm) as the pivot element. Let T (n) denote theworst-case time complexity of this modified quicksort algorithm for sorting n elements.Write down the recurrence formula for T (n).Answer: T (n) = 2T (n2) + O(n).3Problem 4C. (20 points: 4 + 4 + 4 + 4 + 4)A disjoint set structure is given by the following array structure. We are using union byrank and find with path compression.i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16A[i] −3 1 1 3 1 5 5 5 −3 9 9 11 9 13 13 15(4pts) Given the array structure at the top of this page, apply the operation union(7, 16).Write down the resulting array structure in the following table.i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16A[i] 9 1 1 3 1 5 1 5 −4 9 9 11 9 13 9 9(4pts) Given the array structure at the top of this page, apply the operation find-set(8).Write down the resulting array structure in the following table.i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16A[i] −3 1 1 3 1 5 5 1 −3 9 9 11 9 13 13 15(4pts) Given the array structure at the top of this page, apply the operation link(1, 9).Write down the resulting array structure in the following table.i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16A[i] 9 1 1 3 1 5 5 5 −4 9 9 11 9 13 13 15(4pts) Given the array structure at the top of this page, apply the operation union(5, 10).Write down the resulting array structure in the following table.i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16A[i] 9 1 1 3 1 5 5 5 −4 9 9 11 9 13 13 15(4pts) Suppose we are using union by rank and find with path compression. Applyinga total of m operations to a disjoint set with n elements, what is the total numberof basic operations required? You should use asymptotic notation to give the mostaccurate bound.Answer: O(m · α(m, n)).4Problem 5C. (20 points: 5 + 5 + 5 + 5)The following four questions deal with binary search trees.0510152025303540ABCDEFGHIFigure 1: A binary search tree.(5pts) For each of the following sequences, write YES if there exists a binary search tree Tand an integer k such that the search for k will visit exactly the given sequence ofnumbers; write NO otherwise. Please note that this problem has nothing to dowith the tree in Figure 1.(A) 50, 10, 20, 30, 40 YES(B) 15, 20, 30, 40, 50 YES(C) 50, 10, 20, 30, 100 NO(D) 200, 20, 30, 100, 50 YES(E) 50, 100, 20, 30, 40 NO(5pts) Show the sequence obtained by pre-order tree walk of the tree in Figure 1.Answer: A, B, D, E, C, F, H, G, I(5pts) Show the resulting binary search tree obtained by deleting the number 5 from thebinary search tree in Figure 1.(5pts) What is the worst-case …