Mini #2, 15451 Fall 2004 ======================== This mini is due via *email* to your TA, by midnight Tuesday Sept 21. Please use the subject line "15-451 MINI #2" in your email. 1. In class, we discussed a deterministic linear-time algorithm for finding the median (or kth smallest element) of an unsorted array. 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, and why? 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 any array of size 4 using only 4 comparisons? Why or why not?