CSE310 HW04, Thursday, 03/11/2010, Due: Thursday, 03/25/2010Please note that you have to typeset your assignment using either LATEX or MicrosoftWord. Hand-written assignment will not be graded. You need to submit a hardcopybefore the lecture on the due date. You also need to submit an electronic version atthe digital drop box. For the electronic version, you should name your file using theformat HW04-LastName-FirstName.1. (10 pt) Give the exact number of element-wise comparisons needed to find both the smallestand the largest elements in an array of n un-sorted elements.Give the exact number of element-wise comparisons needed to find both the smallest and thesecond smallest elements in an array of n un-sorted elements. Note that you are not supposedto use asymptotic notations to answer these questions.Solution: Let f(n) denote the number of comparisons needed to find both the smallestand the largest elements in an array of n elements. First consider the case where n is even.Let n = 2k. For k = 1, we only need one comparison. Therefore f(2) = 1. Supposewe have computed the largest and the smallest elements among the first 2(k − 1) elements,using f(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 comparison is needed,i.e., f(1) = 0. For k = 1, 2, . . ., f(2k + 1) = f(2k) + 2, because the last element needs tobe compared with both the candidate for largest and the candidate for smallest. Thereforef(2k + 1) = 3k for k = 0, 1, 2, . . .. Combining both cases, we have f(n) = ⌈32n⌉ − 2.Grading:4 pts: if the answer is not perfect, but is32n plus a constant.1 pts: if the answer is 2n − 3.In order to find both the smallest and the second smallest elements in an array, n + log n − 2comparisons are needed.First in n/2 comparisons, we have n/2 groups of 1stand 20candidate for 2ndsmallest in eachgroup. In n/4 comparisons, we have n/4 groups of 1stand 21candidates for 2ndsmallest ineach group. · · · In n/2kcomparisons, we have n/2kgroups of 1stand 2k−1candidates for 2ndsmallest in each group. In 1 comparison, we have 1 group of 1stand 2log ncandidates for 2nd1smallest in the group. We need log n − 1 comparisons to find the 2ndsmallest element in the2log ncandidates. Thus, the total number of comparisons is n + log n − 2.Grading:4 pts: if the answer is not perfect, but is log n plus n plus a constant,1 pts: if the answer is 2n − 3.2. (10 pts) In the linear time select-k algorithm, we used groups of 5. As we discussed in class,we could use groups of r, where r = 3, 4, 5, 6, 7, . . ., although the worst-case running timemay not necessarily linear. Let Tr(n) denote the worst-case time complexity of the algorithmwith groups of r. Derive the recurrence formula for T4(n) and T11(n). You have to prove thebounds on the number of elements in the recursive calls to justify your answer.Solutions: We first concentrate on the derivation of T4(n). An important part of the deriva-tion is to derive a lower bound of the upper left portion of the elements. There are at least⌈⌈n4⌉2⌉ − 2 columns, each with at least 2 elements that are smaller than the median of medians.Therefore the upper left portion contains at leastn4− 4 elements that are smaller than themedian of medians. This leads to the recurrenceT4(n) ≤ T4(⌈n4⌉) + T4(34n + 4) + Θ(n).For group size 11, the upper left portion contains at least ⌈⌈n11⌉2⌉ − 2 columns, each with atleast 6 elements that are smaller than the median of medians. Therefore we haveT11(n) ≤ T11(⌈n11⌉) + T11(811n + 12) + Θ(n).Grading:For each of the two cases, 5pts for perfect answer, 3pts for deriving the correct bound for theupper left portion. No penalty for off by an additive constant in the derivation.3. (10 pts) Let T be the binary search tree illustrated in the rightmost tree in Figure 12.4(b) inthe textbook. In the following questions, each question refers to this tree T , not the resultingtree after some operations.(2 pts) Print out the results of pre-order traversal.Solution: 15, 5, 3, 12, 10, 6, 7, 13, 20, 18, 23.(2 pts) Which node is the successor of the node with value 7?Solution: The node with value 10.2(2 pts) Show the tree after inserting 14 into tree T .Solution: 15, 5, 3, 12, 10, 6, 7, 13, 14, 20, 18, 23.(2 pts) Show the tree after deleting 12 from tree T .Solution: 15, 5, 3, 13, 10, 6, 7, 20, 18, 23.(2 pts) List the element-wise comparisons (in the correct order) for searching 9 in T .Solution: 9 is compared with the following elements: 15, 5, 12, 10Grading: 0/2 for each of the five subquestions.4. (20 pts) Fig. 1 illustrates a red-black tree, where a thick circle represents a black data-bearingnode, a thin circle represents a red data-bearing node, and a thick rectangle represents a blacknil node. In your work, you have to write black near a black node and write red near a red nodeto indicate the colors.0510152025303540455055606528128 43 48 5823Figure 1: A red-black tree.(4 pts) Draw the resulting red-black tree after inserting 56 into the red-black tree in Fig.1. You only have to draw the portion of the tree that is affected.Solution: First, 56 (red) is a left child of 58, after the binary search tree insertion. Thisis case-2. We perform a rotation (rotating away) to get to case-3. Now 56 (red) is theright child of 55, and 58 (red) is the right child of 56. We perform a rotation again.Finally 56 (black) is the left child of 60, 55 (red) is the left child of 56, and 58 (red) isthe right child of 56.(4 pts) Draw the resulting red-black tree after deleting 40 from the red-black tree in Fig.1. You only have to draw the portion of the tree that is affected.Solutions: Since node with value 40 has two children, we slice out its successor, thenode with value 43 and copy the content of the sliced out node to the node originallywith value 40. This is case-2, because 48 is black and has two black (nil) children. We3push the black color up. Here is the part of the tree that is changed. 43 (black) is theleft child of 50. The left child of 40 is 35 (black). The right child of 40 is 45 (black). Theright child of 45 is 48 (red).(4 pts) Draw the resulting red-black tree after deleting 35 from the red-black tree in Fig.1. You only have to draw the portion of the tree that is affected.Solutions: When node 35 is deleted, we have case-1. After