Mini #2, 15451 Spring 2007
                 ==========================

This mini is due via *email* to your TA, by midnight Tuesday, February 6.
Please use the subject line "15-451 MINI #2" in your email.
Your solutions should be submitted IN THE BODY of the email. 
No attachments please.
Include your name and andrew ID at the top of your solutions.

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 every array of size 4 using only 4
comparisons?  Why or why not?

3. Let f(n)=2^n and g(n)=e^n, where e=2.71... is the base of the natural logarithm. 
For the following statements state whether they are true or false. 
Explain your choice.

  (a) f(n)=O(g(n))
  (b) f(n)=o(g(n))
  (c) f(n)=Omega(g(n))
  (d) f(n)= o(2*g(n/lg(e))), where lg is log base 2.