Mini #2, 15451 Fall 2011
                 ========================

This mini is due via *email* to your TA, by 11:59pm Tuesday Sept 20.
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 (or into groups of size 7 which we saw
gave a recurrence T(n) <= T(n/7) + T(5n/7) + cn), we used groups of
size 9 instead. 

(a) What is the recurrence that results?

(b) What does this solve to?


2. Sorting.  

(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 outcomes, a super-comparison has 3! possible outcomes.
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