Jump to content
  • Advertisement
Sign in to follow this  
fengx

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.

If you intended to correct an error in the post then please contact us.

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

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

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

If you intended to correct an error in the post then please contact us.

Guest
This topic is now closed to further replies.
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!