CS344 HW#3

Question 1

We will have two variables relating with the distance dist and min_d, which are initialized to 0.

For the first step of Takeshi’s Castle, we will first assign the minimum distance value between the starting points (lets call the points, \(r_0\) and \(b_0\)), to a variable called dist. To find the minimum distance, we calculate the three possible distance values that correspond with the three possible travel methods:

  1. The distance between \(r_1\) and \(b_1\) (if both players jump at the same time).

  2. The distance between \(r_1\) and \(b_0\) (if only player one jumps).

  3. The distance between \(r_0\) and \(b_1\) (if only player two jumps).

After finding the 3 possible values, we find the miminimum of the 3, and assign it to the min_d variable. Now we will compare the two values min_d and dist. We already know that we need a rope with length dist because that is the initial distance between the two contestants. The question is whether we need a longer rope for the contestants to complete the first jump. If min_d is larger than dist set dist equal to min_d. If min_d is smaller than dist nothing needs to be done because the initial rope length will be long enough to complete the first jump.

Then, we make the contestants do the next iteration of the jump, do the same as above, and find the smallest distance value of the 3 jumps:

  1. The distance between \(r_{i+1}\) and \(b_{k+1}\) (if both players jump at the same time).

  2. The distance between \(r_{i+1}\) and \(b_k\) (if only player one jumps).

  3. The distance between \(r_i\) and \(b_{k+1}\) (if only player two jumps).

Again, once we find the smallest distance value of the 3 jumps (min_d), compare it to the dist variable, and update \(dist\) if necessary. We do this until both contestants reach the end, and \(dist\)’s value is the smallest the rope can be, for the two contestants to finish the challenge.

In the worst case, we have to analyze \(m+n\) jumps because in the worst case at each jump, only one contestant can jump at a time. Also, there needs to be 3 checks and 3 comparisons for each iteration, to calculate the new value of \(min_d\). So in total, there are \(6*(m+n)\) operations, and the run time is \(O(m+n)\).