Youre 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 jarat the moment 70 Chapter 2 Basics of Algorithm Analysis it breaks, you have the correct answerbut you may have to drop it n times (rather than log n as in the binary search solution). So here is the trade-off: it seems you can perform fewer drops if youre willing to break more jars. To understand better how this tradeoff works at a quantitative level, lets consider how to run this experiment given a fixed budget of k 1 jars. In other words, you have to determine the correct answerthe highest safe rungand can use at most k jars in doing so.

PLEASE DESCRIBE A MODEL/DATA STRUCTURE FOR THIS QUESTION including necessary notations, input and output information. For example, if you model the problem as a graph, describe what the nodes and edges represent for respectively. Another example is a tree.

Then present the algorithm details using pseudo code

(b) Now suppose you have a budget of k > 2 jars, for some given k. Describe a strategy for finding the highest safe rung using at most k jars. If fk(n) denotes the number of times you need to drop a jar according to your strategy, then the functions f1, f2, f3,... should have the property that each grows asymptotically slower than the previous one: limn fk(n)/fk1(n) = 0 for each k.