42
« on: September 27, 2008, 02:05:49 am »
This problem is taking directly from my algorithms textbook J. Kleinberg, E. Tardos. "Algorithm Design." Addison-Wesley, 2005. Note: I'm not transcribing it directly.
You're responsible for doing stress testing on jars that your company produces. Sometimes, you have very many jars to spare for worthy testing, in other times, your company is under fiscal strain and can only provide a handful.
The stress test involves a ladder with [tex]n[/tex] rungs. You want to generate a report on each model telling your manager what the highest rung on the ladder is at which you can drop the jar without it breaking. The models tend to have a lot of variance, so say you have no idea at which rung the jar will break. For simplicity's sake, assume that for each model, there exists some rung [tex]k\leqn[/tex] at which a jar of that model will break. Also assume that the jars are identical and that if one jar breaks at a particular rung, all of them will.
a. Imagine you are given an indefinite amount of jars to test. What is the fastest way to find the rung at which the jars of the particular model you're testing break at? Hint: if f(n) is the number of tries you have to take, f(n) is o(n). That is, n dominates f(n) asymptotically, i.e. [tex]\lim_{x\to\infty}\frac{n}{f(n)}=\infty[/tex].
b. If you are given exactly one jar to test, what's the fastest way you can get a definite answer to the problem posed? Hint: there's nothing tricky about this one. It should be fairly obvious.
c. If you are given exactly two jars to test, you can do better than you did in (b). Give a strategy to do this. Hint: when I say better, I don't mean that you do better by some constant amount. The function that tells you the upper bound on the number of tries you have to do given n actually grows much slower than the one that generates the number of moves you have to make in the situation proposed in (b).
d. Generally, if you are given [tex]k[/tex] jars to test, you can get a better bound than if you were given [tex]k-1[/tex] jars. Formally, if [tex]g(n)[/tex] is your bound for [tex]k-1[/tex] jars and [tex]f(n)[/tex] is your bound for [tex]k[/tex] jars, then [tex]f(n)[/tex] is [tex]o(g(n))[/tex]. Give a general strategy for this.
Remarks:
Part (c) and (d) are kind of hard. If you get (c), you should be able to derive (d) with a bit of insight.
Show Posts
