Sign in to follow this  
fengx

Algorithm Questions

Recommended Posts

I had to answer these questions for an algorithm analysis course Im currently taking. Im not sure if the answers I have here are sufficiently valid/correct to satsify as a solution. I would appreciate it if anyone would be able to critique my solutions :) Q: Suppose that you have an N story building and supply of filled water balloons. Suppose also that a water balloon breaks if it is dropped off of floor F or higher, and survives otherwise. Devise a strategy to determine the floor F using at most 1 + lg N drops. A: For this, we would just use a binary search, since the runtime of a binary search is O(logN), which is equal to O(1 + lgN) = O(lgN) = O(logN) Q: Repeat the previous question, but devise a strategy that uses only O(log F) drops. A: First, given an N story building, let us represent each interval of floors by 2^k, where k is the floor at which a water balloon is dropped. If the balloon breaks at a floor 2^k, we know that the balloon will NOT break when dropped at 2^(k-1) floor. Therefore, we can conclude the floor F is 2^k < F < 2^(k-1). Using this inequality: 2^k < F < 2^(k-1) => k-1 < lgF < k => k-1 < lgF => k < lgF + 1 => O(lgF) Finally, we can use a binary search to find our floor F. 2^k - 2^(k-1) = 2*2^(k-1) - 2^(k-1) = 2^(k-1) + 1 = lg2^(k-1) + 1 = k-1 => O(lgF), therefore the # of drops k = O(lgF) Q: Repeat the previous question, but assume you only have two water balloons. Now your goal is to minimize the number of drops. Of course, once you break a water balloon, you can't use it again. Devise a strategy to determine F that involves O(sqrt(N)) drops and guarantees to find F. EXTRA: Do it with only O(sqrt(F)) drops. A: Let N = total # of floors of the building. Let sqrt(N) = interval of floors, with each interval containing sqrt(N) floors. Let k = floor at which the balloon is dropped (or, # of drops, since we will progress linearly floor by floor) since there are sqrt(N) floor intervals: k*sqrt(N) = n for (k=1, 2, 3...sqrt(N)) therefore, at a maximum: k = sqrt(N), which implies k*sqrt(N) = sqrt(N)*sqrt(N) = N since the number of drops k is at most sqrt(N), we conclude k = O(sqrt(N)) For that last question, Im not completely confident my solution is correct. Also, how would I do it with only O(sqrt(F)) drops?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
From the forum FAQ:

9. Do not ask homework related questions. The Gamedev.net members are not here to answer your homework questions, its against the forum rules and few people take kindly to it. Besides, we shouldn't need to tell you that figuring it out for yourself will be way more beneficial to you in the long run.

Share this post


Link to post
Share on other sites
Since you have shown your work, I'll give you a few pointers, but the previous posters are correct: Gamedev isn't the place to ask homework questions.


Quote:
Original post by fengx
For this, we would just use a binary search, since the runtime of a binary search is O(logN), which is equal to O(1 + lgN) = O(lgN) = O(logN)


They want an exact upper bound, not an asymptotic analysis.

Quote:
If the balloon breaks at a floor 2^k, we know that the balloon will NOT break when dropped at 2^(k-1) floor.


If the ballon breaks at floor 2k, all you know is that it will also break at floor n, ∀ n>2k. It says nothing about lower floors. You need to further refine your hypotheses.

Quote:
For that last question, Im not completely confident my solution is correct.


You are on the right track, but your explanation lacks rigour.

Quote:
Also, how would I do it with only O(sqrt(F)) drops?


It's up to you to figure it out.

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.
Sign in to follow this