Problem 1: 

n/7 groups, each of length 7: 

Look at page 38 of the hand-written notes. We get a matrix with 7 
rows and n/7 columns. The size of the top-right portion is 4 times 
n/14, which is 2n/7. Thus, we recurse on a problem of size at most 
5n/7. To compute the median of the medians, we recurse on a problem 
of size n/7. This gives the recurrence

T(n) = n + T(n/7) + T(5n/7). 

Using induction, as on page 40, we can prove that T(n) = O(n). 


n/3 groups, each of length 3: 

Look at page 38 of the hand-written notes. We get a matrix with 3 
rows and n/3 columns. The size of the top-right portion is 2 times 
n/6, which is n/3. Thus, we recurse on a problem of size at most 
2n/3. To compute the median of the medians, we recurse on a problem 
of size n/3. This gives the recurrence

T(n) = n + T(n/3) + T(2n/3). 

In the January 19 tutorial, Problem 6, you have seen that 
T(n) = Theta(n log n). 


Problem 2: 

Let h be the index of the last phase. Then (3/4)^h n = 1. This is 
the same as (4/3)^h = n. Taking logarithms, we get 
h = log_{4/3} n. 

We never used the number of phases, because the total expected running 
time was bounded from above by an infinite series (and this series 
converges). 


Problem 3: 

Break one egg: Drop from floors 1,2,3,4,... until an egg breaks. The 
value of n is the previous floor. The number of eggs that you drop is 
n+1.

Break 2 eggs: Drop eggs from floors 2,4,6,8,... until an egg breaks. 
Let m be such that the egg does not break from floor 2m, but it does 
break from floor 2m+2. Then n is either 2m or 2m+1. So you drop one 
more egg from floor 2m+1. The number of eggs that you drop is 
(m+1)+1=m+2, which is at most (n/2)+2.

Break at most k+c eggs: Drop eggs from floors that are a multiple of 
2^k, until an egg breaks. Let me be such that the egg does not break 
from floor m times 2^k, but it does break from floor (m+1) times 2^k. 
Then

m 2^k <= n < (m+1) 2^k.

So far, we have dropped m+1 eggs, which is at most (n/2^k)+1, and we 
have broken one egg. Now we do a binary search among the floors 
m 2^k , ... , (m+1) 2^k. There are 2^k floors, so we drop 
log (2^k) = k more eggs. Maybe this should be k+1? That is why I 
added "+ a small constant".

Drop O(log n) eggs: You cannot use the previous solution with 
k = log n, because, at the start, you do not know the value of n. 
Here is the trick.

Drop eggs from floors 1,2,4,8,16,32 until an egg breaks. Let m be 
such that the egg does not break from floor 2^m, but it does break 
from floor 2^(m+1). So far, we have dropped m+2 eggs. We know that 
2^m <= n < 2^{m+1}; there are 2^m possible values for n. Note that 
2^(m+1) <= 2n. Thus, we can do a binary search.