Spring 2010 CSE310 Midterm Examination 02B in class Instructions There are ve questions in this paper Please use the space provided below the questions to write the answers Budget your time to answer various questions and avoid spending too much time on a particular question This is a closed book examination You may not consult your books notes NAME ASUID Problems Score P1 P2 P3 P4 P5 Total 0 P1 20 points 10 pts This problem is related to order statistics What is the minimum number of element wise comparisons needed to nd the smallest element and the second smallest element in an un ordered sequence of n elements Do not use asymptotic notation in your answer Solution In order to nd 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 1st and 20 candidate for 2nd smallest in each group In n 4 comparisons we have n 4 groups of 1st and 21 candidates for 2nd smallest in each group In n 2k comparisons we have n 2k groups of 1st and 2k 1 candidates for 2nd smallest in each group In 1 comparison we have 1 group of 1st and 2 log n candidates for 2nd smallest in the group We need log n 1 comparisons to nd the 2nd smallest element in the 2 log n candidates Thus the total number of comparisons 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 sequence 8 4 7 3 6 2 5 1 to illustrate the process for nding the smallest element and the second smallest element Show all the element wise comparisons made for this example in the correct order Solution The order of element wise comparisons is as follows To nd the smallest element 8 4 7 3 6 2 5 1 4 3 2 1 3 1 To nd 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 that we are using the linear time selection algorithm with group size 5 Suppose that we have 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 is the 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 recurrence n 7n T5 n T5 T5 6 b n 5 10 for some constant b What is the recurrence formula of the running time T7 n for the corresponding 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 upper n left portion of the elements There are at least 27 2 columns each with at least 4 elements that are smaller than the median of medians Therefore the upper left portion contains at least 4n 8 elements that are smaller than the median of medians This 14 leads to the recurrence n 5 T7 n T7 T7 n 8 bn 7 7 Grading Keys 5 pts for correct answer 2 pts for including either the rst or the second term of the recurrence 1 pts will be cut o for incorrect const in the second term of the recurrence 2 P2 20 points The following four questions deal with binary search trees A 25 B 15 D 0 40 C E 20 30 F H 10 G 50 45 I Figure 1 A binary search tree 5 pts For each of the following sequences write YES if there exist a binary search tree T and an 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 the tree 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 1 Solution 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 I Grading Keys 5 pts for correct answer 5 pts Show the resulting binary search tree obtained by inserting the number 43 into the binary search tree in Figure 1 Solution The binary search tree after inserting 43 is as follows 3 25 15 0 40 20 30 50 10 45 43 Grading Keys 5 pts for correct answer 5 pts Show the resulting binary search tree obtained by deleting node B from the binary search tree in Figure 1 Solution The binary search tree after deleting node B is as follows 25 20 40 0 30 10 50 45 Grading Keys 5 pts for correct answer 4 P3 20 points The following four questions deal with red black trees 30 15 50 5 0 25 10 8 20 40 28 35 60 45 55 65 13 Figure 2 A red black tree where a thick circle represents a black node and a thin circle represents 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 xup which property of the red black tree is violated Solution Before the insertion xup 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 xup You can show only part of the tree that can illustrate the changes Solution The part of resulting red black tree after insertion xup is as follows 5 30 50 60 55 65 57 Grading 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 xup which property of the red black tree is violated Solution Before the deletion xup 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 xup You can show only part of the tree that can illustrate the changes Solution The part of resulting red black tree after the deletion xup is as follows 6 30 15 5 0 25 10 8 28 13 Grading Keys 5 pts for correct answer 7 P4 20 points 8 pts Let the array …
View Full Document
Unlocking...