Computer Science

Dynamic Programming

Egg Dropping

     

Consider the standard 2-egg problem. We wish to determine the critical height at which an egg breaks. That is we assume that there is some critical height CC, such that if we drop an egg from height hCh \leq C the egg does not break where as it will always break if dropped from height h>Ch > C. We want to minimize the number of trials and we are only given two eggs.

Let us consider the worst case scenario. Let W(k)W(k) be the minimum number of trials required to identify CC under the worst case scenario given that we have two eggs and a building a height kk.

How many values of k>0k > 0 satisfy W(k)=18518505W(k) = 18518505 ?

Consider the classic egg drop problem. Let S(n,k)S(n,k) be the minimum number of egg droppings that will suffice to find the critical floor in an nn-story building given kk eggs.

S(k,n)S(k,n) can be described as follows for an elementary function of nn, f(n)f(n).

S(k,n)=Θ(f(n,k))S(k,n) = \Theta(f(n,k))

The function f(n,k)f(n,k) is given by which of the following?

Consider the standard egg dropping problem, and design an algorithm that computes the maximum number of trials required to find the critical floor in the worst case. Find the maximum number of trials required in the worst case when you have three eggs and 105105 floors to check.

×

Problem Loading...

Note Loading...

Set Loading...