Suppose you are testing the resiliency of a type of jar when it is dropped. Assu

Question

Suppose you are testing the resiliency of a type of jar when it is dropped. Assume there exists some height h (an integral number of feet) such that dropping a jar from any height greater than or equal to h will break the jar, but dropping a jar from any height less than h will not break the jar.
Now assume you have a ladder with n rungs at distances 1; 2; ...; n feet above the ground. You know that h <= n. You are asked to design an algorithm for finding h using this ladder; in particular, you are asked to design some sequence of heights h1; h2; ...such that climbing the ladder to heights hi (in order of the sequence), dropping a jar, and observing whether the jar breaks or not, allows you to determine the value of h (possibly before reaching the end of the sequence). The time complexity of such an algorithm counts its worst-case number of drops before detecting h, and we care about evaluating the time in terms of n. Assume that you can re-use the jar in future drops if it does not break, and that the re-use does not affect the resiliency of the jar.
(a) Suppose you are allowed to break only one jar. Give the best (meaning, best O() time in terms of n) algorithm you can for detecting h, and justify its running time.
(b) Suppose you are allowed to break any number of jars. Give the best algorithm you can for detecting h, and justify its running time.
(c) Suppose you are allowed to break at most two jars. Give an algorithm to detect h with a strictly sublinear (better than O(n)) running time.

Explanation / Answer

Found at http://eclipse.wells.edu/badams/courses/cs322/solutions/files/hw1-solution.pdf Find a jar-testing algorithm for a budget of 2 jars that

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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