Fall 2013 CSE310 Midterm 2B (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 1B. (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] 18 16 14 12 10 8 6 4 2 0Suppose you are applying the linear time buildheap algorithm to build a min-heap fromthe 10 elements of array A. For i = 5, 4, 3, 2, 1, show the array structure after the call tomin-heapify(A, i) is completed, using the table provided below.• After min-heapify(A, 5), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 18 16 14 12 0 8 6 4 2 10• After min-heapify(A, 4), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 18 16 14 2 0 8 6 4 12 10• After min-heapify(A, 3), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 18 16 6 2 0 8 14 4 12 10• After min-heapify(A, 2), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 18 0 6 2 10 8 14 4 12 16• After min-heapify(A, 1), the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 0 2 6 4 10 8 14 18 12 161Problem 2B. (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] 0 2 4 6 8 10 12 14 16 18Suppose 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] 0 2 4 6 8 10• After inserting the first 7 elements, the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 0 2 4 6 8 10 12• After inserting the first 8 elements, the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 0 2 4 6 8 10 12 14• After inserting the first 9 elements, the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 0 2 4 6 8 10 12 14 16• After inserting the first 10 elements, the array structure is:i 1 2 3 4 5 6 7 8 9 10A[i] 0 2 4 6 8 10 12 14 16 182Problem 3B. (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 13, 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:19n26+ 14.(5pts) Let T13(n) denote the worst-case time complexity of your algorithm. Write down therecurrence formula for T13(n).Answer: T13(n) = T13(n13) + T13(19n26+ 14) + bn.(5pts) Use the asymptotic notations to denote T13(n) as a function of n.Answer: T (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.Use the asymptotic notations to denote T (n) as a function of n.Answer: T (n) = O(n log n).3Problem 4B. (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 7 −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 7 −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 1 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 7 −4 9 9 11 9 13 9 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 7 −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 5B. (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) 20, 30, 40, 50, 10 No(B) 30, 40, 50, 15, 20 No(C) 20, 30, 100, 50, 10 No(D) 30, 100, 50, 200, 20 No(E) 20, 30, 40, 50, 100 Yes(5pts) Show the sequence obtained by in-order tree walk of the tree in Figure 1.Answer: D, B, E, A, F, H, C, I, G.(5pts) Show the resulting binary search tree obtained by deleting the number 30 from thebinary search tree in Figure …