perform in the worst case in order to identify the highest floor from which we can safely drop an egg out of an n-floor building when given k eggs. Notably, if E(n, k) represents the solution to the Egg Drop problem with n floors and k eggs, E(n, k) satisfies the following recurrence:

with base cases E(n, k) = n if k = 1, n = 0, or n = 1. Use this recurrence to answer the following questions about developing an iterative dynamic programming algorithm for the Egg Drop problem (E(n, k)).

1. Describe how you would iterate through the dynamic programming data structure in an iterative dynamic programming algorithm. Your answer may be given in spatial terms (e.g., left-to-right) or as one or more for loops.

2. Give pseudocode for an iterative dynamic programming algorithm for the Egg Drop problem.

3. Can the space complexity of the iterative algorithm be reduced relative to the memoized algorithm? If so, how? If not, why not?

E(n, k min max(E(n- i, k), E(i, k -1