Mini #2, 15451 Spring 2009
                 ==========================

This mini is due via *email* to your TA, by 11:59pm Tuesday, Feb 3.
Please use the subject line "15-451 MINI #2" in your email.
Also, please copy your answers directly into the email body.
*Do not* include any attachments.

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?

(c) Now imagine instead of breaking the array into groups of five or
seven, you break it into groups of three. Write the recurrance, and
show that it is not O(n).

2. Comparison-Based Sorting
Mergesort can sort any array of 4 elements using at most 5 comparisons.
This seems pretty fast. Which of the following algorithms can get by
with fewer than 5 comparisons?
a) Insertion sort
b) Bubble sort
c) Selection sort
d) Randomized quicksort
List all that apply and please explain your answer.

3. More comparison-based sorting
In class, we saw that any comparison-based sorting algorithm
requires at least lg(n!) comparisons. This is one of the oldest
results in computer science, coming from a time when a computer
could only compare two elements at once.

Nowadays, computers have many CPU cores and so they can compare
several elements in one step. To be concrete, let's say that
our computer can compare 5 numbers at once, and return them
in sorted order. Does this change the lower bound for sorting?
Please explain.
[Hint: Try reworking the lower bound proof with regular
2-element comparisons, and then 3-element comparisons first]