8. You\'re doing some stress-testing on various models of glass jars to determin

Question

8. You're doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with n rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung n/4 or 3n/4 depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar-at the moment

Explanation / Answer

Answer: The first strategy based on binary search is "Divide-and-Conquer" strategy, while the other strategy is based on "Linear Probing".

Keeping the trade-off of both these strategies in mind, the new strategy will be a mix of both the strategies. It can be described as follows:

Strategy: Under this strategy, we will first drop the jar from mid rung. If jar is broken, then we will follow linear probing starting from first rung with next to mid rung as the upper limit and will check one rung at a time provided number of drops is within permissible limit.

If jar is not broken, then we will drop it from mid rung of upper sigment of ladder and choose an appropriate option (linear probe or further divide and conquer) depending on the result.

This strategy will be emulated till we are able to find highest rung.

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.