ONLY NEED ANSWER FOR PART B! A) Throwing eggs from a building. Suppose that you
ID: 3786719 • Letter: O
Question
ONLY NEED ANSWER FOR PART B!
A) Throwing eggs from a building. Suppose that you have an N-story building and
plenty of eggs. Suppose also that an egg is broken if it is thrown off floor F or higher,
and unhurt otherwise. First, devise a strategy to determine the value of F such that the
number of broken eggs is ~lg N when using ~lg N throws, then find a way to reduce the
cost to ~2lg F.
B) Throwing two eggs from a building. Consider the previous question, but now
suppose you only have two eggs, and your cost model is the number of throws. Devise
a strategy to determine F such that the number of throws is at most 2N, then find a
way to reduce the cost to ~c F. This is analogous to a situation where search hits (egg
intact) are much cheaper than misses (egg broken).
Explanation / Answer
To achieve 2 * sqrt(N), drop eggs at floors sqrt(N), 2 * sqrt(N), 3 * sqrt(N), ..., sqrt(N) * sqrt(N). (For simplicity, we assume here that sqrt(N) is an integer.) Let assume that the egg broke at level k * sqrt(N). With the second egg you should then perform a linear search in the interval (k-1) * sqrt(N) to k * sqrt(N). In total you will be able to find the floor F in at most 2 * sqrt(N) trials.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.