Mini #2, 15451 Fall 2012 ======================== This mini is due via *email* to your TA, by 11:59pm Tuesday Sept 18. 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? (explain your reasoning) (b) What does this solve to? 2. Sorting. [this is an old test question] (a) It is possible to sort an array of 3 elements using at most 3 comparisons. Why does this not contradict the Omega(n log n) lower bound for sorting? (b) Suppose we have a sorting algorithm that in addition to regular comparisons, is also allowed super-comparisons: a super-comparison takes in *three* elements and outputs those elements in order from smallest to largest. So, unlike a regular comparison that only has two possible answers, a super-comparison has 3! possible answers. Which of the following is a correct lower bound on the number of super-comparisons needed to sort an array of size n? (and give a brief explanation why) log_2(n!) log_3(n!) log_6(n!) n^2