The Egg Drop problem asks us to find the fewest number of egg dropping trials we

Question

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 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: E(n, k) = min i=1,...,n max(E(n ? i, k), E(i, k ? 1)) , 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 program- ming 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? 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 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: E(n, k) = min i=1,...,n max(E(n ? i, k), E(i, k ? 1)) , 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 program- ming 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? 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 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: E(n, k) = min i=1,...,n max(E(n ? i, k), E(i, k ? 1)) , 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 program- ming 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?

Explanation / Answer

1st part

In the egg drop problem from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn’t break.

1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.

Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials.

2nd part

3rd part

In an iterative solution the same sub problem is called again and hence it has an overlaping sub problem property. So the recomputations of the same sup problem can be avoided by using a temporary array and processing in a bottom up manner.

For example =>

Hence,

Time Complexity: O(nk^2)
Space Complexity: O(nk) in dynamic programming.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.