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.
Suppose that we modify mergesort to cutoff to insertion sort when the file
size is M or smaller. Give a formula for the average number of comparisons,
assuming that both the file size N and the cutoff value M are powers of two.
Extra credit: Find the value of M (power of two) that minimizes the
average number of comparisons.