Algorithms - 1 Egg 100 floors

Question

Im currently doing a puzzle in my book Algorithhms 4th Edition by Robert Sedgewick and Kevin Wayne, and this puzzle is about the classic Egg Dropping problem.

The book doesn't cover much of it, and Im having a hard time understanding how the logic here works. But, there are three questions in the book that goes kind of like this:

Presume that we have a story building with N-floors, and presume that an egg will break if you drop it from floor F(F ≤ N) or higher, but the egg will NOT break if you drop it from any floor lower than this. We know the value of N, and now we are going to figure out the value of F.

a.) Presume that we have loads of eggs to try this out with. Think of a strategy to figure out F by crushing ∼ lg N eggs.

b.) Improve the strategy by only using ∼ 2 lg F eggs.

c.) Now we presume that we only have one egg. Think of a strategy to figure out the value of F by dropping the egg ∼ F times.

---

Now my assumption - for the answer of a.) - is that it will take log2(100) ≈ 6,64 eggs/7 egg drops (≈7 eggs) if I where to have 100 floors (cause it's easier to count) using a binary search?! or am I totally wrong?

The b.) answer I don't really understand.

And c.) Will be F = F dropps, since we only have one egg it will be crushed on the "Fth" floor. If the height of the floor we are dropping the egg from, starting at level 0, doesn't break the egg, then we try floor 1, and if the egg doesn't break there either we try floor 2 and so on and so on... It will be a linear search.

Have any of you all come across this type of problem before and what do you make of it? (this is my first semester studying algorithms and data structures, so I'm a novice at this 110%).

Thanks!

Answer 1

For A you are correct it would take at most log(N) eggs to figure out which floor the egg would break, since we can do a binary search to figure out the floor

Part B can be thought of in this way, Suppose the egg breaks at the x'th floor, we can just try dropping the 2nd egg from floor 1 to x-1 in a linear way, Now Suppose I am at x'th floor and the egg doesn't break, next I can try making the egg fall from x-1 floors above the current floor. So that we have to search only x-1 floors next time, similarly for x-2

x + (x-1) + (x-2) + (x-3) + .... + 1 = N

would be the worst case. And you can calculate x easily using the above equation.

for part C we would have to traverse each floor since we can't find it in any other way. We only have 1 egg and we have to exactly find out the floor

Answer 2

This is my own solution I hope it makes sense to you:

a.) Yes you are right, using binary search gives directly O(lg N) bound to find F

c.) Yes you are right, just try from 1st floor until F-th floor and the only egg breaks while you find F in ~F drops

---

b.) It is where my dirty thought starts:

Drop the egg from 1st floor, then 3rd floor, then 7-th, then 15-th...Until it breaks.

What I am testing is the Summation of (2^i) where i >= 0

Let x be the floor Summation(2^x) which just before the egg breaks. Then we have

Summation(2^x) <= F <= Summation(2^(x+1))

Now we can see that finding x is using lg(Sum(2^x)) = O(lg F)

Then we can use binary search in range [Sum(2^x), Sum(2^(x+1))],

This will use O(lg (Sum(2^(x+1)) - Sum(2^x))) = O(lg (2^(x+1))) = O(lg (Sum(2^x) + 1)) = O(lg F)

Together we should get 2O(lg F)

---

PS:

I think 2O(lg F) can be worse than O(lg N) when F*F > N. So it is quite confusing if the question statement said it is a "improved strategy"

PS2:

I am dumb. Actually you can just use the same method but test 1,2,4,8...2^x floor and the same implication will hold which gives 2O(lg F). I don't know why my first thought is using summation which makes things complicated :(