perform in the worst case in order to identify the highest floor from which we c

Question

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?

Explanation / Answer

Hello Student!

I am happy to help you!

1.

Consider n to be the floor from where you wants to drop the egg and you only have k trials.

So basically we can say

E(n, k) = 1 + min{max(E(n-1, x-1}, E(n, k-x))}

For x = 1, 2... till k.

1. The algorithm works like this -

For n = 2 and k = 36

2. Here goes the code -

E(n, k) {

// A two dimensional array which stores the minimum trials
// needed by i number of eggs from the jth floor
int EggFloor[n+1][k+1];

for (int i = 1; i <= n; i++) {
// If there is one floor only one trial is needed
EggFloor[i][1] = 1;
// If there is no floor zero trials
EggFloor[i][0] = 0;
}
for (int i = 1; i <= k; i++) {
// A single egg means that number of trials
EggFloor[1][i] = i;
}

// Filling all the egg drop table
for (int i = 2; i <= n; i++) {
// Here, i is the number of eggs
for (int j = 2; j <= k; j++) {
// Here, j is the number of floor
EggFloor[i][j] = INT_MAX;
for (int x = 1; x <= j; x++) {
// output appended

// Same as the recurrence relation formula in the ques
int output = 1 + max(EggFloor[i-1][x-1], EggFloor[i][j-x]);
if (output < EggFloor[i][j])
// max is stored
EggFloor[i][j] = output;
}
}
}

// Result is returned
return EggFloor[n][k];
}

Time complexity - O(n^3)

Space complecity - O(n^2)

3. This statement is confusing because if we are making an iterative algorithm therefore we need to store the old information as well. If we are storing that information then we will be needing atleast O(n^2) space. Therefore, it is not possible to reduce the space complexity of the algorithm more than O(n^2).

Thank you. Feel free to ask anything. If you like the answer. Please upvote it. It means a lot. Thank you again.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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