Spring 2010 CSE310 Midterm Examination 02B (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 second smallestelement in an un-ordered sequence of n elements? Do not use asymptotic notation inyour answer.Solution:In order to find both the smallest and the second smallest elements in an array, n +⌈log n⌉ − 2 comparisons are needed.First in n/2 comparisons, we have n/2 groups of 1stand 20candidate for 2ndsmallestin each group. In n/4 comparisons, we have n/4 groups of 1stand 21candidates for2ndsmallest in each group. · · · In n/2kcomparisons, we have n/2kgroups of 1stand2k−1candidates for 2ndsmallest in each group. In 1 comparison, we have 1 group of 1stand 2⌈log n⌉candidates for 2ndsmallest in the group. We need ⌈log n⌉ − 1 comparisonsto find the 2ndsmallest element in the 2⌈log n⌉candidates. Thus, the total number ofcomparisons is n + ⌈log n⌉ − 2.Grading Keys:5 pts for correct answer;3 pts for the answer of the form n + log n + const;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 second smallest el-ement. Show all the element-wise comparisons made for this example, in the correctorder.Solution:The order of element-wise comparisons is as follows:To find the smallest element: (8, 4), (7, 3), (6, 2), (5, 1), (4, 3), (2, 1), (3, 1)To find the second smallest element: (3, 2), (2, 5)Grading Keys:+0.5 pts for each correct comparison.0.5 bonus pts for all correct comparisons.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;). 1, 2, 3, 4, 5; 6, 7, 8, 9, 10; 11, 12, 13, 14, 15; 16, 17, 18, 19, 20; 21, 22, 23, 24, 25. What isthe median of medians?Solution:The median of medians is 13.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 T7(n) for thecorresponding select-k algorithm if we use groups of size 7.Solutions: An important part of the derivation is to derive a lower bound of the upperleft portion of the elements. There are at least ⌈⌈n7⌉2⌉ − 2 columns, each with at least 4elements that are smaller than the median of medians. Therefore the upper left portioncontains at least4n14− 8 elements that are smaller than the median of medians. Thisleads to the recurrenceT7(n) ≤ T7(⌈n7⌉) + T7(57n + 8) + 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 30404550ABCDE F GI25152010HFigure 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) 1, 10, 100, 50, 5(B) 1, 10, 100, 50, 55(C) 100, 50, 30, 20, 10(D) 100, 50, 30, 20, 1000(E) 100, 50, 300, 20, 1Solution:(A) No; (B) Yes; (C) Yes; (D) No; (E) No.Grading Keys:1 pts for each correct answer.(5 pts) Show the sequence obtained by pre-order tree walk of the tree in Figure 1.Solution:The sequence obtained by pre-order tree walk of the tree is: A, B, D, H, E, C, F, G, IGrading Keys:5 pts for correct answer.(5 pts) Show the resulting binary search tree obtained by inserting the number 43 into thebinary search tree in Figure 1.Solution:The binary search tree after inserting 43 is as follows:32550301043200401545Grading Keys:5 pts for correct answer.(5 pts) Show the resulting binary search tree obtained by deleting node B from the binarysearch tree in Figure 1.Solution:The binary search tree after deleting node B is as follows:255030100402045Grading 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 57 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 have black 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:5506555605730Grading Keys:5 pts for correct answer.(10 pts) Suppose we want to delete the node with key 20 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:6301082551501328Grading Keys:5 pts for correct answer.7P4. (20 points)(8 pts) Let the array form of the disjoint sets be as follows.A |-3 | 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(7, 14).Solution:After the operation union(7, 14), the array form is as follows:A | 8 | 1 | 1 | 3 | 1 | 5 | 1 |-4 | 8 | 8 |10 | 8