In the Egg Drop problem, we are given some number of eggs (k), and we are tasked with finding the highest floor of an n-story building from which we can drop an egg without breaking. The Egg Drop problem asks us to find the fewest number of egg dropping trials we need to perform in the worst case in order to identify this floor on an n-floor building when given k eggs.

In the base case, if we only have k = 1 egg, we must test every floor one by one in order to identify this floor, which takes n trials in worst case. Thus, EggDrop(n, 1) = n.

As another example, if we have 2 eggs and 6 floors, we can identify the floor using 3 trials in the worst case, as shown in the diagram below:

1. Using the recurrence, give a small example demonstrating why the Egg Drop problem is a good candidate for dynamic programming.

2. What implementation would you recommend for a dynamic programming algorithm for the Egg Drop problem? Briefly justify your answer.

3. Give pseudocode for a na ??ve recursive algorithm (i.e., non-dynamic pro- gramming algorithm) for E(n, k).

4. Give pseudocode for a memoized dynamic programming algorithm for E(n,k).

Drop egg from 3rd floor No Drop from 5th floor Drop from 1st floor No Broken? Broken?Yes No Yes Drop from 6th floor Drop from 4th floor Drop from 2nd floor No Broken?Yes No Broken? Yes Broken?Yes It can be shown that if E(n, k) represents the solution to the Egg Drop problem with n floors and k eggs, then E(n, k) satisfies the following recurrence: E(n,k)-mn lmax(E-ik)E) ?1, ,n with base cases E(n, k-if k-1, -0, or n-1. Use this recurrence to answer the following questions about developing a memoized dynamic program ming algorithm for the Egg Drop problem (E(n,k))