Mini #2, 15451 Fall 2010
            ========================

This mini is due via *email* to your TA, by 11:59pm Tuesday, Sep 14.
Please use the *exact* subject line "15-451 MINI #2" in your email. As always make sure include your name and andrew id.

Also, we prefer that you copy your answers directly into the email body, instead
of including attachments. Thanks!


1) MEDIAN-13
In the lecture, we saw the analysis for an algorithm that found the median of a
set of elements by first partitioning the elements into groups of 5 and finding
the median of each of those groups. This algorithm is called DeterministicSelect
and is described in the notes for Lecture 4.  

Suppose we modify the algorithm to partition the elements into groups of 13. 

Median-13 algorithm:
1. Partition the set into n/13 groups of size 13 and find the median of each group.
2. Recursively, find the median of the medians. Call this p.
3. Use p as a pivot to split the array into subarrays LESS and GREATER.
4. Recurse on the appropriate piece.

Give and solve the recurrence relation for this modified algorithm. It is
sufficient to give your solution in the big-Oh notation.


2) KNOCKOUT TOURNAMENT
A knockout tournament, such as the NCAA March Madness Basketball Championship,
is performed in rounds. In each round the teams each play exactly one game and
the winners of those games progress, while the losers are knocked out of the
competition. So, in each round, exactly half of the teams are eliminated. At
the completion of the tournament, there is one winner who is undefeated. 
Assuming that when two teams play each other the outcome is always the same 
and assuming transitivity (A beats B and B beats C implies A would beat C),
how many more games would have to be played to always find a second place winner?

We need the exact number, not an asymptotic bound! For "ceils" and "floors" of
a quantity q, you can use ceil(q) and floor(q) or any other "clear and
understandable" notation.
Hint: You may want to review the lecture notes.


3) LOG IS COOL!
You are given two sorted lists, L1 and L2, of combined length n (>= 1). Let 1 <= k <= n. Assume that
   (i)   all the n elements are distinct,
   (ii)  both L1 and L2 are sorted in increasing order,
   (iii) both L1 and L2 have length at least k,
   (iv)  each comparison is of cost 1,
   (v)   every non-comparison operation is free,
   (vi)  lg stands for logarithm to the base 2 and
   (vii) n and k are powers of 2

We would like to use the following algorithm to find the k^th smallest (also
known as the k^th order statistic) of all the n elements.

   1. L_SMALLEST(L1, L2, k)
   2.   if (k = 1) /* checking if k=1 *DOES NOT COUNT* as a comparison! */
   3.     compare the smallest elements of L1 and L2 and return the smaller
   4.   k1 = (k/2)^th smallest of L1
   5.   k2 = (k/2)^th smallest of L2
   6.   if (k1 < k2)
   7.     throw away the k/2 elements of L1 less than or equal to k1 (including k1) resulting in L1'
   8.     throw away all the elements of L2 greater than k2 resulting in L2'
   9.   else
  10.     throw away the k/2 elements of L2 less than or equal to k2 (including k2) resulting in L2'
  11.     throw away all the elements of L1 greater than k1 resulting in L1'
  12.   L_SMALLEST(L1', L2', k/2)

  a) Explain why the recursive call at line 12 is correct, i.e. the order
statistic is halved.
  b) Give a recurrence for the number of comparisons in the above algorithm
and solve it for the exact number. Remember that we want the "exact" number
and an asymptotic bound will not suffice.