Mini #2, 15451 Fall 2008
                 ========================

This mini is due via *email* to your TA, by 11:59pm Tuesday Sept 16.
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?

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?

In addition, attached is an anonymous feedback form - we are
interested in your opinions on the pace and other aspects of the
course.  Please fill it out and hand it in in lecture this coming Tues
(Sept 16).