Stress Testing Jars Puzzle

[Sidoh]

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.

[Camel]

I assume O is worst case, not average case?
Does the jar always break on rung n?


[edit] Obvoiusly, for a, you make a btree out of the rungs, O(ln(n)). The only way to do b with one jar is to start at the bottom, O(n)

[Sidoh]

I assume O is worst case, not average case?
Does the jar always break on rung n?


[edit] Obvoiusly, for a, you make a btree out of the rungs, O(ln(n)). The only way to do b with one jar is to start at the bottom, O(n)

Yeah, we only care about worst case here.

Those are the correct answers for (a) and (b).  It's probably more clear to say "you do binary search on the ladder" for (a).

[rabbit]

A) Binary search
B) Linear search
C/D) I still haven't sat down and figured these out.

[Camel]

Let's say, for example, n=10, and k=2;

An obvious place to start would be the middle, at rung 5 -- but what happens if the jar breaks there? You've only got one jar left, and you have to do a linear search on 5 rungs, which is O(n). It should then be apparent that the starting point needs to be dependent on the number of jars.

In order to minimize the number of tests, we need to put an equal value on each of the jars, so we'll create a tiered system. Let N be the iterative magnatude for the Kth jar.

If k=2, it makes sense to let N=sqrt(n), thus setting an equal amount of work for each of the jars. If n=16, N=4; resulting in up to 4 tests for the first jar, and up to 3 for the second jar.

It seems logical, for part D, to infer that N=n^(1/k); though it must be noted that N will vary for each jar, and that N only gives you the second to last jar.

Nk := 1, per part B, linear search of whats left
N(k-1) = n^(1/k)
..

More generally,
Nx = n^((k-x)/k)

[Sidoh]

Let's say, for example, n=10, and k=2;

An obvious place to start would be the middle, at rung 5 -- but what happens if the jar breaks there? You've only got one jar left, and you have to do a linear search on 5 rungs, which is O(n). It should then be apparent that the starting point needs to be dependent on the number of jars.

In order to minimize the number of tests, we need to put an equal value on each of the jars, so we'll create a tiered system. Let N be the iterative magnatude for the Kth jar.

If k=2, it makes sense to let N=sqrt(n), thus setting an equal amount of work for each of the jars. If n=16, N=4; resulting in up to 4 tests for the first jar, and up to 3 for the second jar.

It seems logical, for part D, to infer that N=n^(1/k)

N should be something along the lines of n^(1/k), or the "kth root" of n.

The analysis isn't very clear, but that's the right answer for part C.  The answer for D, however, isn't quite there.

[Camel]

Mistake in transcription; edited.

[Sidoh]

There we go.  That's kind of an awkward way to define, it, but I think I buy it.

Here's some nice pseudo-code for a recursive definition.


k <-- The number of jars available to you
n <-- The size of the ladder
s <-- From what rung you will begin your test on (assume the steps are 0-indexed)
JarStressTest(k, n, s) :
   step_size <- n^((k - 1)/k)
   current_step <- 0
   while TestJar(s + (current_step * step_size)) != JAR_BROKEN
      current_step <- current_step + 1
   done

   if step_size == 1 then
      return (current_step - 1)
   else
      return JarStressTest((k - 1), n, (s + ((current_step - 1) * step_size)))
   fi


For the analysis, let us first think about the bound on the number of times the while loop will execute.  To do this, we need to see how long it will take current_step*step_size to get to n.  Since step_size is [tex]n^{\frac{k-1}{k}}[/tex], we have that [tex]n^{\frac{1}{k}}n^{\frac{k-1}{k}}=n[/tex], so we do [tex]\Theta(n^{\frac{1}{k}})[/tex] work.  So far, we have that our algorithm is [tex]\Omega(n^{\frac{1}{k}})[/tex], meaning that it runs AT FASTEST [tex]\Theta(n^{\frac{1}{k}})[/tex].  Now, we have to look at the work that we have remaining.

Since the step size is [tex]n^{\frac{k-1}{k}}[/tex], we have that many rungs left to check.  However, since each recursive call reduces the number of steps it must check in the same way, we have that we must do [tex]n^{\frac{1}{k}}+(n^{\frac{k-1}{k}})^{\frac{1}{k-1}}=2n^{\frac{1}{k}}[/tex], which is [tex]\Theta(n^{\frac{1}{k}})[/tex].

[Camel]

That's the basic algorithm I used, except my step_size is defined differently:

k <-- The number of jars you start with
x <-- The current jar (starting at 1)
n <-- The size of the ladder
s <-- From what rung you will begin your test on (assume the steps are 0-indexed)
JarStressTest(x, s) :
   step_size <- n^((k - x)/k)
   current_step <- 0
   while TestJar(s + (current_step * step_size)) != JAR_BROKEN
      current_step <- current_step + 1
   done

   if step_size == 1 then
      return (current_step - 1)
   else
      return JarStressTest(x+1, (s + ((current_step - 1) * step_size)))
   fi

[Sidoh]

Yeah, it's the same thing. The introduction of x makes it a bit more awkward to define recursively, though.

[Camel]

Given:
[tex]\displaystyle
N_x = n^{\frac{k-x}{k}}[/tex]

Number of tests for step x:
[tex]\displaystyle
T_x =
\frac{rungs\_in\_test_x}{N_x} =
\frac{N_{x-1}}{N_x} =
\frac{n^{\frac{k-x+1}{k}}}{n^{\frac{k-x}{k}}} =
n^\frac{1}{k}
[/tex]

...so, [tex]\displaystyle\sum_{x=1}^{k}{T_x} = k*n^\frac{1}{k}[/tex] which comes to [tex]\Theta(n^\frac{1}{k})[/tex]

[Camel]

I have a hunch that you can't do what you've done. You're determining the time complexity of each iteration correctly, but your k value changes with each iteration, so you can not simply sum Tx in terms for your definition of k from 1 to k.

Your solution; my variable definitions (that is, k is the number of jars you started with, and x is the one you're trying to break right now):
[tex]\displaystyle
N_x = n^{\frac{k - x - 1}{k - x}}[/tex]
For simplicity, let's let z=k-x
[tex]\displaystyle
N_x = n^{\frac{z - 1}{z}} \newline
T_x = \frac{N_{x-1}}{N_x} =
\frac
{n^{\frac{z}{z + 1}}}
{n^{\frac{z - 1}{z}}} =
n^{\frac{z}{z + 1} - \frac{z - 1}{z}}
[/tex]

..and it doesn't get much cleaner than that. I don't think I have enough paper to determine the summation of Tx.

My solution was designed to define T such that it does not vary with x, which is equivalent to distributing the "work" over each of the jars. I'm not quite sure what the goal of defining your step size the way you did was - can you elaborate?