You are given m identical eggs and an n story building. You need to figure out...

Transcribed Image Text:

You are given m identical eggs and an n story building. You need to figure out the highest floor l {0, 1, 2,... n} that you can drop an egg from without breaking it. Each egg will never break when dropped from floor or lower, and always breaks if dropped from floor l+1 or higher. ( = 0 means the egg always breaks). Once an egg breaks, you cannot use it any more. However, if an egg does not break, you can reuse it. Let f(n, m) be the minimum number of egg drops that are needed to find l (regardless of the value of l). (a) Find f(1,m), ƒf(0, m), f(n,1), and f(n,0). Briefly explain your answers. (b) Consider dropping an egg at floor x when there are n floors and m eggs left. Then, it either breaks, or doesn't break. In either scenario, determine the minimum remaining number of egg drops that are needed to find in terms of f(·,·), n, m, and/or x. (c) Find a recurrence relation for f(n,m). Hint: whenever you drop an egg, call whichever of the egg breaking/not breaking leads to more drops the "worst-case event". Since we need to find l regardless of its value, you should assume the worst-case event always happens. (d) If we want to use dynamic programming to compute f(n, m) given n and m, in what order do we solve the subproblems? (e) Based on your responses to previous parts, analyze the runtime complexity of your algorithm. (f) Analyze the pace complexity of your DP algorithm. (g) (Extra Credit) Is it possible to modify your algorithm above to use less space? If so, describe your modification and re-analyze the space complexity. If not, briefly justify. DP You are given m identical eggs and an n story building. You need to figure out the highest floor l {0, 1, 2,... n} that you can drop an egg from without breaking it. Each egg will never break when dropped from floor or lower, and always breaks if dropped from floor l+1 or higher. ( = 0 means the egg always breaks). Once an egg breaks, you cannot use it any more. However, if an egg does not break, you can reuse it. Let f(n, m) be the minimum number of egg drops that are needed to find l (regardless of the value of l). (a) Find f(1,m), ƒf(0, m), f(n,1), and f(n,0). Briefly explain your answers. (b) Consider dropping an egg at floor x when there are n floors and m eggs left. Then, it either breaks, or doesn't break. In either scenario, determine the minimum remaining number of egg drops that are needed to find in terms of f(·,·), n, m, and/or x. (c) Find a recurrence relation for f(n,m). Hint: whenever you drop an egg, call whichever of the egg breaking/not breaking leads to more drops the "worst-case event". Since we need to find l regardless of its value, you should assume the worst-case event always happens. (d) If we want to use dynamic programming to compute f(n, m) given n and m, in what order do we solve the subproblems? (e) Based on your responses to previous parts, analyze the runtime complexity of your algorithm. (f) Analyze the pace complexity of your DP algorithm. (g) (Extra Credit) Is it possible to modify your algorithm above to use less space? If so, describe your modification and re-analyze the space complexity. If not, briefly justify. DP

Answer rating: 100% (QA)

a Here are the values of fn m for the given cases f1 m You have only one egg In the worst case youll ... View the full answer