NAME:
LOGIN:
PRECEPT:
COS 226 Exercises on Analysis of Algorithms
1.
Suppose that you have an N story building and a carton of eggs.
Suppose also that a egg breaks if it is dropped off of floor F or higher,
and survives otherwise.
Devise a strategy to determine the floor F using at most 1 + lg N drops.
2.
Repeat the previous question, but devise a strategy that uses
only O(log F) drops.
3.
Repeat the previous question, but assume you only have two eggs.
Now your goal is to minimize the number of drops. Of course, once you
break an egg, you can't use it again.
Devise a strategy
to determine F that involves O(sqrt(N)) drops and guarantees to find F.
4. [purely for fun and not to be turned in]
Repeat the previous question, but with only O(sqrt(F)) drops.