Question

Sometimes, brute force is the best we can do. Consider the following prob- lem:

You live in a building of n floors. Someone keeps throwing eggs out of a balcony on some unknown floor f . At each time slot, this person will throw an egg. At each time slot, you can go to a balcony on any floor and attempt to save the egg. If the balcony you chose is below the thrower’s, you save the egg. If, however, the balcony you chose is above the thrower’s, the egg falls, breaks, and you lose the game. If the floor you chose is the same as the thrower’s, you catch him and you win, saving the next generation of eggs.

1. Write a brute-force algorithm that will always win in this game without losing any eggs in the minimum number of time-slots. The input to your algorithm should be the number of floors n, and the output should be an array X of n integers, one integer for each time-slot. The entry X[i] determines which floor your algorithm will go to, at time-slot i.
2. A more efficient algorithm would catch the thrower in fewer time-slots than yours. Argue that there should not be a more efficient algorithm.
3. Prove that if any algorithm A₂ faster than yours exists, there will be some instance of this problem where A₂ looses.

Answer 1

This problem can be easily solved using the divide and conquer paradigm if we could sacrifice some eggs. Here is an algorithm that solves this problem in minimum possible time-slots (log2n in the worst case).

Algorithm:-

Input: n = number of floors

1. Check on the middle floor. If this floor is the same as the thrower, we catch him.

2. If we fail to catch the thrower and the egg, the thrower is in the lower half of the building. So, recur to the lower half.

3. If we catch the egg, then the thrower is in the upper half of the building. So, recur to the upper half.

Time complexity:-

Best case: O(1), when the thrower is found on the middle floor

Average & Worst Case: O(log2n)

This is the fastest way to catch the thrower.

But since we cannot lose any egg. So the only option is to go linearly from the lowermost floor to the thrower's floor (n in the worst case).

Algorithm:-

Input: n = number of floors

Output: X = array of floors we checked.

1. Go to the ground floor.

2. Add the floor number to X. If you found the thrower, break.

3. else go up. Go to step 2.

Time complexity:-

Best case: O(1), when the thrower is found on the ground floor.

Average and Worst case: O(n), when the thrower is on the top floor.

No efficient algorithm than this is possible. We want to catch the thrower without losing any egg.

Suppose there is an algorithm A that is better than our algorithm M.

Invariant: No egg is lost. That is, Catcher is never above the thrower.

=> A can find the thrower in less than n comparisons.

=> A will skip some floors.

=> Thrower can be

1. At the skipped floor: If this is the case, then we know that if we hadn't skipped this one, we could have got him in fewer comparisons using M.
2. Below the skipped floor: Algorithm M also skips such floors. So here, both M and A are equal.
3. Above the skipped floor: In this case, if the Catcher is above the thrower, then we lost an egg, which violates our invariant.

Hence, No algorithm efficient than our algorithm can catch the thrower in less than n comparisons without losing eggs.