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?

Answer 1

(Ans-)

1) Optimal Substructure:
When we drop an egg 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.

  k ==> Number of floors
  n ==> Number of Eggs
  eggDrop(n, k) ==> Minimum number of trials needed to find the critical
                    floor in worst case.
  eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): 
                 x in {1, 2, ..., k}}

2) Overlapping Subproblems

It should be noted that the above function computes the same subproblems again and again. See the following partial recursion tree, E(2, 2) is being evaluated twice. There will many repeated subproblems when you draw the complete recursion tree even for small values of n and k.

                         E(2,4)
                           |                      
          ------------------------------------- 
          |             |           |         |   
          |             |           |         |       
      x=1/          x=2/      x=3/     x=4/ 
        /             /         ....      ....
       /             /    
 E(1,0)  E(2,3)     E(1,1)  E(2,2)
          /  /...         /  
      x=1/                 .....
        /    
     E(1,0)  E(2,2)
            /   
            ......

Partial recursion tree for 2 eggs and 4 floors.

Since same suproblems are called again, this problem has Overlapping Subprolems property. So Egg Dropping Puzzle has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array eggFloor[][] in bottom up manner.

Ans-2)

Dynamic Programming Solution
Following are the implementations for Egg Dropping problem using Dynamic Programming.

• C++
• Java
• Python
• C#
• PHP

# A Dynamic Programming based C++ Program for the Egg Dropping Puzzle # include <stdio.h> # include <limits.h> // A utility function to get maximum of two integers int max(int a, int b) { return (a > b)? a: b; } /* Function to get minimum number of trials needed in worst   case with n eggs and k floors */ int eggDrop(int n, int k) {     /* A 2D table where entery eggFloor[i][j] will represent minimum        number of trials needed for i eggs and j floors. */     int eggFloor[n+1][k+1];     int res;     int i, j, x;     // We need one trial for one floor and0 trials for 0 floors     for (i = 1; i <= n; i++)     {         eggFloor[i][1] = 1;         eggFloor[i][0] = 0;     }     // We always need j trials for one egg and j floors.     for (j = 1; j <= k; j++)         eggFloor[1][j] = j;     // Fill rest of the entries in table using optimal substructure     // property     for (i = 2; i <= n; i++)     {         for (j = 2; j <= k; j++)         {             eggFloor[i][j] = INT_MAX;             for (x = 1; x <= j; x++)             {                 res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);                 if (res < eggFloor[i][j])                     eggFloor[i][j] = res;             }         }     }     // eggFloor[n][k] holds the result     return eggFloor[n][k]; } /* Driver program to test to pront printDups*/ int main() {     int n = 2, k = 36;     printf ("nMinimum number of trials in worst case with %d eggs and "              "%d floors is %d n", n, k, eggDrop(n, k));     return 0; } Ans-3) //RECURSIVE SOLUTION: # include <stdio.h> # include <limits.h> // A utility function to get maximum of two integers int max(int a, int b) { return (a > b)? a: b; } /* Function to get minimum number of trials needed in worst   case with n eggs and k floors */ int eggDrop(int n, int k) {     // If there are no floors, then no trials needed. OR if there is     // one floor, one trial needed.     if (k == 1 || k == 0)         return k;     // We need k trials for one egg and k floors     if (n == 1)         return k;     int min = INT_MAX, x, res;     // Consider all droppings from 1st floor to kth floor and     // return the minimum of these values plus 1.     for (x = 1; x <= k; x++)     {         res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));         if (res < min)             min = res;     }     return min + 1; } /* Driver program to test to pront printDups*/ int main() {     int n = 2, k = 10;     printf ("nMinimum number of trials in worst case with %d eggs and "              "%d floors is %d n", n, k, eggDrop(n, k));     return 0; } Ans-4) //Psuedo code in python:- def solvepuzzle(N,k): for i = 1 to N numdrops(i,1) = 1 numdrops(i,0) = 0 end for for i=1 to k numdrops(1, i) = i end for for i = 2 to N for j = 2 to k numdrops[i][j] = ? minimum = ? for x = 1 to j minimum = min(minimum, 1 + max(numdrops(i-1,x-1),numdrops(i,j-x)) ) end for numdrops[i][j] = minimum end for end for return numdrops(N,k)