Mini #2, 15451 Spring 2005 ========================== This mini is due via *email*, by 11:59pm Tue, Feb. 7th. PLEASE NOTE: all students (of both sections) should email their answers for this mini to Daniel Golovin . When submitting, please use the subject line "15-451 MINI #2" in your email. If you have a question, please use the subject line "15-451 MINI #2 QUESTION" in your email. 1. Recall the deterministic linear-time algorithm for finding the median (or kth smallest element) of an unsorted array, which can be found in the notes, chapter 4. Our analysis of this algorithm gave the recurrence: T(n) <= T(n/5) + T(7n/10) + cn. Suppose we changed the algorithm so that rather than breaking up the array into groups of size 5, we used groups of size 7 instead. (a) What is the recurrence that results? (b) What does this solve to? 2. Sorting. (a) Show that it is possible to sort any array of 4 elements using only 5 comparisons. Note: there are multiple correct ways to do this. (b) Is it possible to sort every array of size 4 using only 4 comparisons? Why or why not? 3. Binary Search Trees. (a) In addition to Find, Insert and Delete, suppose that we also want to support the following operation: Key_at_position(k) Return the key that's stored in the kth position (they are numbered 1, 2, 3....n) in a binary search tree, in symmetric (left ---> right) order. What additional field(s) would you have to keep in the tree to accommodate this operation efficiently? Briefly explain the algorithm for this operation using the field(s) you propose. (b) Suppose that we wanted to efficiently support the following operation: Sum_Range(i,j) Return the sum of the keys that are in positions i....j. Where "position" is defined as in part (a). What additional fields (over what you used in part a) would be required to do this efficiently? Briefly explain the algorithm for this operation using the field(s) you propose. By "efficient" in this problem we mean O(log n).