RECITATION NOTES	   15-451 Algorithms		      09/14/11

* go over practice quiz
* problem related to Thurs lecture last week.
* getting tight upper/lower bounds for some problem

=======================================================================
Problem related to Thurs lecture:
We saw in lecture by a "stack of bricks" argument that a recurrence of
the form: 

  T(n) = n + T(a1 * n) + T(a2 * n) + ... + T(ak * n)

(for constants a1,...,ak) solves to O(n) so long as a1 + ... + ak < 1.

What about a recurrence like:

  T(n) = n^2 + T(a1 * n) + T(a2 * n) + ... + T(ak * n)
or
  T(n) = n^b + T(a1 * n) + T(a2 * n) + ... + T(ak * n)

What conditions on the ai do you need so that this gives O(n^b)?

[Answer we just need a1^b + ... + ak^b < 1.  Let's define "r" to be
this quantity.  Looking at the "stack of bricks" argument, each time
you move down one level, each brick gets replaced by something r times
its size.  So, the sum of sizes of the bricks at each level is r times
the sum at the previous level.  This means the total work down is a
decreasing geometric series.]

============================================================================

Here is a variation on the 20-questions problem.  Say I choose a
number between 1 and N and you want to guess it in as few questions as
possible (each time you make an incorrect guess, I'll tell you if it
is too high or too low).  As we all know, the strategy for this
problem that minimizes the worst-case number of guesses is to do
binary search.  But, what if you are only allowed ONE guess that is
too high?  Can you still solve the problem in o(N) guesses?  [If you
were not allowed *ANY* guesses that are too high, the only option you
would have would be to guess 1,2,3,... in order].

Any ideas?   

[Another way to state the problem: you want to figure out how many
centimeters high you can drop an egg without it breaking, and you only
have two eggs...]

Here's a strategy: guess 1, sqrt(N), 2*sqrt(N),..., until you get to
some (i+1)*sqrt(N) that's too high.  Now we know the number is between
[i*sqrt(N) and (i+1)*sqrt(N)] so we can finish it off in sqrt(N)
guesses.  Total is at most 2*sqrt(N).

Can you show an Omega(sqrt(N)) lower bound for any deterministic algorithm?
What if the algorithm makes a guess g_i that is at least sqrt(N)
larger than any previous guess?  What if the algorithm *never* makes
such a guess?


Want to try an upper/lower bound if you're allowed *two* guesses that
are too high?
  [Ans: Theta(n^{1/3})]

=======================================================================