Spring 2010 CSE310 Midterm Examination 02A (in class)Instructions:• There are five questions in this paper. Please use the space provided (below thequestions) to write the answers.• Budget your time to answer various questions and avoid spending too much time on aparticular question.• This is a closed book examination. You may not consult your books/notes.NAMEASUIDProblems ScoreP1P2P3P4P5Total0P1. (20 points)(10 pts) This problem is related to order statistics. What is the minimum number ofelement-wise comparisons needed to find the smallest element and the largest elementin an un-ordered sequence of n elements? Do not use asymptotic notation in youranswer.Solution:Let f (n) denote the number of comparisons needed to find both the smallest and thelargest elements in an array of n elements. First consider the case where n is even. Letn = 2k. For k = 1, we only need one comparison. Therefore f(2) = 1. Suppose we havecomputed the largest and the smallest elements among the first 2(k−1) elements, usingf(2k − 2) comparisons. For the next two elements, we need 3 comparisons. Thereforef(2k) = f(2k − 2) + 3. This leads to f(2k) = 3k − 2 for k = 1, 2, . . ..Now consider the case where n is odd. Let n = 2k + 1. For k = 0, no comparisonis needed, i.e., f (1) = 0. For k = 1, 2, . . ., f(2k + 1) = f (2k) + 2, because the lastelement needs to be compared with both the candidate for largest and the candidatefor smallest. Therefore f(2k + 1) = 3k for k = 0, 1, 2, . . .. Combining both cases, wehave f(n) = ⌈32n⌉ − 2.Grading Keys:5 pts for correct answer;4 pts for the answer of the form3n2+ const;3 pts for the answer3n2;1 pts for the answer 2n − 3.Use the sequence8, 4, 7, 3, 6, 2, 5, 1to illustrate the process for finding the smallest element and the largest element. Showall the element-wise comparisons made for this example, in the correct order.Solution:The sequence of element-wise comparisons are: (8, 4), (7, 3), (8, 7), (3, 4), (6, 2), (8,6), (3, 2), (5, 1), (8, 5), (1, 2).Grading Keys:+0.5 pts for each correct comparison.1(10 pts) This problem is related to the linear time selection algorithm. Assume thatwe are using the linear time selection algorithm with group size 5. Suppose that wehave 25 numbers and that they have been grouped into 5 groups of size 5 (separated by;). 8, 9, 10, 11, 12; 22, 21, 20, 19, 18; 28, 29, 30, 31, 32; 40, 38, 39, 41, 42; 50, 48, 49, 51, 52.What is the median of medians?Solution:The median of medians is 30.Grading Keys:5 pts for correct answer.When we used groups of size 5, we have obtained the recurrenceT5(n) ≤ T5(⌈n5⌉) + T5(7n10+ 6) + b × nfor some constant b. What is the recurrence formula of the running time T9(n) for thecorresponding select-k algorithm if we use groups of size 9.Solutions:An important part of the derivation is to derive a lower bound of the upper left portionof the elements. There are at least ⌈⌈n9⌉2⌉ − 2 columns, each with at least 5 elementsthat are smaller than the median of medians. Therefore the upper left portion containsat least5n18− 10 elements that are smaller than the median of medians. This leads tothe recurrenceT9(n) ≤ T9(⌈n9⌉) + T9(1318n + 10) + bn.Grading Keys:5 pts for correct answer;2 pts for including either the first or the second term of the recurrence;1 pts will be cut off for incorrect const in the second term of the recurrence.2P2. (20 points) The following four questions deal with binary search trees.0 3035404550ABCDE F GJ K2515201810H IFigure 1: A binary search tree.(5 pts) For each of the following sequences, write YES if there exist a binary search tree T andan integer k such that the search for k will visit exactly the given sequence of numbers;write NO otherwise. Please note that this problem has nothing to do with thetree in Figure 1.(A) 90, 80, 50, 100(B) 400, 100, 300, 200(C) 80, 100, 50, 25(D) 100, 200, 300, 150(E) 100, 200, 150, 250Solution:(A) No; (B) Yes; (C) No; (D) No; (E) No.Grading Keys:1 pts for each correct answer.(5 pts) Show the sequence obtained by post-order tree walk of the tree in Figure 1.Solution: The sequence obtained by post-order tree walk of the tree is: H, D, I, E,B, J, F, K, G, C, A.Grading Keys:5 pts for correct answer.(5 pts) Show the resulting binary search tree obtained by inserting the number 6 into thebinary search tree in Figure 1.Solution:The binary search tree after inserting 6 is as follows:3255030106200401518 3545Grading Keys:5 pts for correct answer.(5 pts) Show the resulting binary search tree obtained by deleting node C from the binarysearch tree in Figure 1.Solution:The binary search tree after deleting node C is as follows:25503010200451518 35Grading Keys:5 pts for correct answer.4P3. (20 points) The following four questions deal with red-black trees.05101520253035404550556065288 13Figure 2: A red-black tree, where a thick circle represents a black node and a thin circlerepresents a red node. Only the data-bearing nodes are shown.(10 pts) Suppose we want to insert number 9 into the red-black tree in Figure 2.– Before the insertion-fixup, which property of the red-black tree is violated?Solution: Before the insertion-fixup, property 4(every red node can only haveblack children) is violated.Grading Keys:5 pts for correct answer.– Show the resulting red-black tree after the insertion-fixup. You can show onlypart of the tree that can illustrate the changes.Solution:The part of resulting red-black tree after insertion-fixup is as follows:513810095Grading Keys:5 pts for correct answer.(10 pts) Suppose we want to delete the node with key 0 from the red-black tree in Figure 2.– Before the deletion-fixup, which property of the red-black tree is violated?Solution:Before the deletion-fixup, property 1(every node is either red or black) is violated.Grading Keys:5 pts for correct answer.– Show the resulting red-black tree after the deletion-fixup. You can show only partof the tree that can illustrate the changes.Solution:The part of resulting red-black tree after the deletion-fixup is as follows:15813510Grading Keys:5 pts for correct answer.6P4. (20 points)(8 pts) Let the array form of the disjoint sets be as follows.A |-4 | 1 | 1 | 3 | 3 | 5 | 5 |-3 | 8 | 8 |10 |10 |12 |12 |i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 |14 |Assume that we are using union by rank and find with path compression. Show thearray form of the resulting disjoint sets after the operation union(6, 13).Solution:After the operation