Answer Happy

Jars on a ladder problem. Given a ladder of n rungs and k identical glass jars, one has to design an experiment of dropping jars from certain rungs, in order to find the highest rung (HS) on the ladder from which a jar doesn't break if dropped. Idea: With only one jar (k=1), we can't risk breaking the jar without getting an answer.So we start from the lowest rung on the ladder, and move up. When the jar breaks, the previous rung is the answer; if we are unlucky, we have to do all n rungs, thus n trials.Now lets think of k=log(n): with log(n) or more jars, we have enough jars to do binary search, even if jars are broken at every rung. So in this case we need log(n) trials.Note that we can't do binary search with less than log(n) jars, as we risk breaking all jars before arriving at an answer in the worst case. Your task is to calculate q = MinT(n, ) = the minimum number of dropping trials any such experiment has to make, to solve the problem even in the worst/unluckiest case (i.e., not running out of jars to drop before arriving at an answer). MinT stands for Minimum number of Trials. A(5 points). Explain the optimal solution structure and write a recursion for MinT(n, k). B(5 points). Write the alternative/dual recursion for MaxR(k, q) = the Highest Ladder Size n doable with k jars and maximum q trials. Explain how MinT(n, k) can be computed from the table MaxR(k, q). MaxR stands for the Maximum number of Rungs. C(10 points). For one of these two recursions (not both, take your pick) write the bottom-up non-recursive computation pseudocode. Hint: the recursion MinT(n, k) is a bit more difficult and takes more computation steps, but once the table is computed, the rest is easier on points E-F below. The recursion in MaxR(q, k) is perhaps easier, but trickier afterwards: make sure you compute all cells necessary to get MinT(n, k) - see point B. D(10 points). Redo the computation this time top-down recursive, using memoization. E(10 points). Trace the solution. While computing bottom-up, use an auxiliary structure that can be used to determine the optimal sequence of drops for a given input n, k. The procedure TRACE(n, k) should output the ladder rungs to drop jars, considering the dynamic outcomes of previous drops. Hint: its recursive. Somewhere in the procedure there should be an if statement like “if the trial at rung x breaks the jar... else ..."