Spring 2010 CSE310 Midterm Examination 02A 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 largest element in an un ordered sequence of n elements Do not use asymptotic notation in your answer Solution Let f n denote the number of comparisons needed to nd both the smallest and 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 Suppose we have computed the largest and the smallest elements among the rst 2 k 1 elements using f 2k 2 comparisons For the next two elements we need 3 comparisons Therefore f 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 to be compared with both the candidate for largest and the candidate for smallest Therefore f 2k 1 3k for k 0 1 2 Combining both cases we have f n 23 n 2 Grading Keys 5 pts for correct answer 4 pts for the answer of the form 3 pts for the answer 3n 2 1 pts for the answer 2n 3 3n 2 const Use the sequence 8 4 7 3 6 2 5 1 to illustrate the process for nding the smallest element and the largest element Show all 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 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 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 recurrence 7n n T5 n T5 T5 6 b n 5 10 for some constant b What is the recurrence formula of the running time T9 n for the corresponding 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 portion n of the elements There are at least 29 2 columns each with at least 5 elements that are smaller than the median of medians Therefore the upper left portion contains at least 5n 10 elements that are smaller than the median of medians This leads to 18 the recurrence n 13 T9 n T9 T9 n 10 bn 9 18 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 H 10 40 C E 20 30 F 18 I J 35 G 50 45 K 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 90 80 50 100 B 400 100 300 200 C 80 100 50 25 D 100 200 300 150 E 100 200 150 250 Solution 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 the binary search tree in Figure 1 Solution The binary search tree after inserting 6 is as follows 3 25 15 40 0 20 10 30 18 50 45 35 6 Grading Keys 5 pts for correct answer 5 pts Show the resulting binary search tree obtained by deleting node C from the binary search tree in Figure 1 Solution The binary search tree after deleting node C is as follows 25 15 45 0 20 10 30 18 50 35 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 9 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 0 10 8 13 9 5 Grading 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 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 …
View Full Document
Unlocking...