Public Group

# Algorithm Questions

This topic is 4415 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
Hmm I don't think that many people here are interested in taking a look at peoples homework. Just a small hint.

##### Share on other sites
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 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 fengxFor 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 on other sites

This topic is 4415 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

This topic is now closed to further replies.

• 37
• 12
• 10
• 10
• 9
• ### Forum Statistics

• Total Topics
631360
• Total Posts
2999556
×