CPSC 331 —Solutions for Assignment #1 This problem concerned the problem of counting the number of routes from one point to an- other along a grid of city streets. It involved the number Routes(n, m) of ways to travel n blocks to the east and m blocks to the north of an origin point, for non-negative integers n and m. It was argued that this is equal to the value that is given by the following recurrence: For n,m ∈ N, Routes(n,m) = { 1 if n = 0 or m = 0 (or both), Routes(n− 1,m) + Routes(n,m− 1) if n > 0 and m > 0 This was used to define the following computational problem. Route Counting Precondition: A pair of nonnegative integers, n and m, are given as input. Postcondition: The value Routes(n,m) (as defined above) is returned as output. A simple recursive algorithm sRoute that can be used to solve this problem is shown in Fig- ure 1 on page 2. 1. You were asked to prove that the function f(n,m) = (n+ m) is a bound function for this recursive algorithm. Solution: This function is a well-defined integer-valued function of the inputs n and m for this algorithm. The algorithm only calls itself recursively (twice) at line 3. In the first recursive application m is not changed but the value of n is decreased by one, so that the value of f(n,m) = n+m is decreased by one as well. Similarly, in the second recursively application n is not changed but the value of m is decreased by one, so that the value of f(n,m) = n + m is decreased by one, once again. Thus the value of this function is decreased by (at least) one every time the function calls itself recursively. Suppose that the precondition for the “Route Counting” problem is satisfied but that f(n,m) ≤ 0 — that is, n + m ≤ 0. Since the precondition is satisfied n ≥ 0 and m ≥ 0, 1 int sRoute(int n, int m) { 1. if ((n == 0) or (m == 0)) { 2. return 1 } else { 3. return sRoute(n − 1, m) + sRoute(n, m− 1) } } Figure 1: A Recursive Solution for the “Route Counting” Problem so n = m = n + m = 0. The test at line 1 is therefore passed and the execution of the algorithm halts, after the execution of the step at line 2, without the algorithm calling itself recursively. Since the conditions in the definition of a “bound function for a recursive algorithm” are satisfied it follows that the function f is a bound function for this recursive algorithm, as claimed. 2. You were asked to prove that the sRoute algorithm correctly solves the “Route Counting” problem. Solution: One can see by inspection of the code that this algorithm does not access or modify any inputs or global data and does not generate any outputs mentioned in the specification of the “Route Counting” problem, that is, it has no undocumented side- effects. It is, therefore, necessary and sufficient to prove the following. Claim: Let n and m be non-negative integers. It the sRoute algorithm is executed with inputs n and m (so that the precondition for the “Route Counting” problem is satisfied) then this execution of the algorithm eventually ends, and Routes(n, m) is returned as output. Proof. The result will be proved by induction on n+m. The standard form of mathematical induction will be used. Basis: If n+m = 0 and the precondition for the “Route Counting” problem is satisfied, so that n ≥ 0 and m ≥ 0, then n = m = n+ m = 0. It follows that if the algorithm is executed with these inputs then the test at line 1 is passed and the value 1 = Routes(n,m) is returned after the execution after the step at line 2 (when the algorithm terminates), as needed to satisfy the claim in this case. Inductive Step: Let k be an integer such that k ≥ 0. It is necessary and sufficient to use the following 2 Inductive Hypothesis: Let n and m be non-negative integers such that n + m = k. If the sRoute algorithm is executed with n and m as inputs then this execution of the algorithm eventually ends, and Routes(n, m, i)s returned as output. to establish the following Inductive Claim: Let n and m be non-negative integers such that n+m = k+1. If the sRoute algorithm is executed with n and m as inputs then this execution of the algorithm eventually ends, and Routes(n, m, i)s returned as output. With that noted, suppose that n and m are non-negative integers such that n+m = k+1, and consider an execution of the sRoute algorithm with n and m as input. Either n = 0, m = 0, or n,m ≥ 1. These cases are considered separately below. • Case: n = 0. In this case the test at line 1 is passed and the execution of the algorithm ends after the execution of the step at line 2 — with Routes(n,m) = 1 returned as output, as needed to establish the Inductive Claim in this case. • Case: m = 0. Once again, the test at line 1 is passed and the step at line 2 is executed, ending the algorithm with Routes(n,m) = 1 returned, as desired. • Case: n,m ≥ 1. In this case the test at line 1 fails and execution continues with the step at line 3. Execution continues with a recursive application of the algorithm with inputs n − 1 and m. Now, since n,m ≥ 1 the precondition of the “Route Counting” problem is satisfied when this recursive execution begins — and, since (n − 1) + m = (n + m)− 1 = k it follows by the Inductive Hypothesis that this execution of the algorithm eventually ends with Routes(n− 1,m) returned as output. This is followed by a recursive application of the algorithm with inputs n and m− 1. Once again, since n,m ≥ 1 the precondition for the “Route Counting” problem is satisfied Since n+ (m− 1) = (n+ m)− 1 = k it follows by the Inductive Hypothesis that this execution of the algorithm eventually ends with Routes(n,m − 1) returned as output. An examination of the code confirms that this execution of the algorithm also ends, with Routes(n− 1,m) + Routes(n,m− 1) returned as output. Since n,m ≥ 1 it follows by the definition of this function that this is equal to Routes(n,m), this establishes the Inductive Claim in this case too. The Inductive Claim has been established in every possible case — as needed to com- plete the Inductive Step, and to prove the claim. 3 3. You were asked to write a Java program Routes1.java that implements this algorithm. Information about the signature of the method and how both the main method and an inner method would handle various failure situations, were included in the instructions for the question. Solution: A Java program Routes1.java that meets these requirements is now avail- able. 4. For non-negative integers n and m let TRoutes1(n,m) be the number of numbered steps that are executed by the algorithm in Figure 1, given n and m as inputs. You were asked to write a recurrence for TRoutes1(n,m). Solution: If either n = 0 or m = 0 then the test at line 1 is passed and the execution of the algorithm ends after the execution of the test at line 2, so that two steps are executed. If n,m ≥ 1 then the test at line 1 fails and the text at line 3 is executed, instead. However, this includes two recursive applications of the algorithm — one with inputs n− 1 and m, and the other with inputs n and m− 1. It follows that, for all inputs n,m ∈ N, TRoutes1(n,m) = { 2 if n = 0 or m = 0, TRoutes1(n− 1,m) + TRoutes1(n,m− 1) + 2 if n,m ≥ 1. Note: It follows by the above that TRoutes1(0, 0) = TRoutes1(0, 1) = TRoutes1(1, 0) = 2, since at least one of the inputs is 0 in each of these cases. It also follows by the above recurrence that TRoutes1(1, 1) = TRoutes1(0, 1) + TRoutes1(1, 0) + 2 (since both of the inputs are positive) = 2 + 2 + 2 (since TRoutes1(0, 1) = TRoutes1(1, 0) = 2) = 6, as claimed. 5. It is follows by its definition that TRoutes1(n,m) ≥ 0 for all n,m ∈ N. You were asked to use your recurrence, and the above observation (which you may use without proof) to show that TRoutes1(n, n) ≥ 2 n for all n ∈ N. Solution: It is necessary to prove the following. 4 Claim: If TRoutes1 : N 2 → N such that, for all n,m ∈ N, TRoutes1(n,m) = { 2 if n = 0 or m = 0, TRoutes1(n− 1,m) + TRoutes1(n,m− 1) + 2 if n,m ≥ 1, then TRoutes1(n, n) ≥ 2 n for all n ∈ N. Proof. This will be proved by induction on n. The
standard form of mathematical induc- tion will be used. Basis: If n = 0 then TRoutes1(n, n) = TRoutes1(0, 0) = 2 (by the recurrence for TRoutes1 in the claim) ≥ 1 = 20 = 2n as needed to establish the claim in this case. Inductive Step: Let k be an integer such that k ≥ 0. It is necessary and sufficient to use the following Inductive Hypothesis: TRoutes1(k, k) ≥ 2 k. to prove the following Inductive Claim: TRoutes1(k + 1, k + 1) ≥ 2 k+1. With that noted, let k ∈ N. Either k = 0 or k ≥ 1. These cases are considered separately, below. Case: k = 0. In this case TRoutes1(k + 1, k + 1) = TRoutes1(1, 1) = TRoutes1(0, 1) + TRoutes1(1, 0) + 2 (by the given recurrence, since 1 ≥ 1) = 2 + 2 + 2 (since TRoutes1(0, 1) = TRoutes1(1, 0) = 2, by the above recurrence) = 6 ≥ 4 = 21 = 2k+1 as needed to establish the Inductive Claim in this case. 5 Case: k ≥ 1. In this case TRoutes1(k + 1, k + 1) = TRoutes1(k, k + 1) + TRoutes1(k + 1, k) + 2 (by the given recurrence, since k + 1 ≥ 1) = (TRoutes1(k − 1, k + 1) + TRoutes1(k, k) + 2) + (TRoutes1(k, k) + TRoutes1(k + 1, k − 1) + 2) + 2 (by the given recurrence, since k − 1, k ≥ 1) = TRoutes1(k + 1, k − 1) + 2× TRoutes1(k, k) + TRoutes1(k − 1, k) + 6 (re-ordering and collecting terms) ≥ 2× TRoutes1(k, k) + 6 (since TRoutes1(k + 1, k − 1) ≥ 0 and TRoutes1(k − 1, k + 1) ≥ 0) ≥ 2× TRoutes1(k, k) ≥ 2× 2k (by the Inductive Hypothesis) = 2k+1 as needed to establish the Inductive Claim in this case as well. Since the Inductive Claim has been established in every possible case this completes the Inductive Hypothesis. The result now follows, by induction on n. The next questions for this exercise considered the algorithm shown in Figure 2 on page 7. When answering the next question, you were allowed to assume that the following is a loop invariant for the outer loop in this algorithm (at lines 5–12) without proving it. Loop Invariant for Outer Loop (a) n and m are integer inputs such that n ≥ 1 and m ≥ 1. (b) R is a (variable) ((n+ 1)× (m+ 1)) array of integers. (c) i is an integer variable such that 0 ≤ i ≤ n+ 1. (d) R[k][ℓ] = Routes(k, ℓ) for all integers k and ℓ such that 0 ≤ k ≤ i − 1 and 0 ≤ ℓ ≤ m. 6. You were asked to state a loop invariant for the inner loop (at lines 7–11) and prove that your loop invariant is correct. 6 int sRoute2(int n, int m) { 1. if ((n == 0) or (m == 0)) { 2. return 1 } else { 3. Set R to be an ((n+ 1)× (m+ 1)) array of integer’s. 4. integer i := 0 5. while (i ≤ n) { 6. integer j := 0 7. while (j ≤ m) { 8. if ((i == 0) or (j == 0)) { 9. R[i][j] := 1 } else { 10. R[i][j] := R[i − 1][j] + R[i][j − 1] } 11. j := j+1 } 12. i := i+1 } 13. return R[n][m] } } Figure 2: A Faster Algorithm for the “Route Counting” Problem Solution: A loop invariant for the outer loop is as follows. Loop Invariant for Inner Loop (a) n and m are integer inputs such that n ≥ 1 and m ≥ 1. (b) R is a (variable) ((n+ 1)× (m+ 1)) array of integers. (c) i is an integer variable such that 0 ≤ i ≤ n. (d) R[k][ℓ] = Routes(k, ℓ) for all integers k and ℓ such that 0 ≤ k ≤ i − 1 and 0 ≤ ℓ ≤ m. (e) j is an integer variable such that 0 ≤ j ≤ m+ 1. (f) R[i][ℓ] = Routes(i, ℓ) for every integer ℓ such that 0 ≤ ℓ ≤ j− 1. To see that this is correct, consider any point during an execution of this algorithm starting with its problem’s precondition satisfied, when the beginning of this inner loop is reached. 7 This is part of an execution of the body of the inner loop, and it can be assumed that the loop invariant for the outer loop is satisfied at the beginning of this execution of the inner loop body. Parts (a) and (b) of the inner loop body are also parts of the outer loop body, and these concern the inputs n and m, as well as the type and dimensions of the array R. Neither n, m nor R are changed when the steps at line 6 is executed, so parts (a) and (b) of the loop invariant are still true when the inner loop is reached. Since part (c) of the loop invariant also holds when the execution of the body of the inner loop begins, i is an integer variable such that 0 ≤ i ≤ n+ 1 at this point. Furthermore the test for the outer loop at line 5 must have been checked, such that i ≤ n as well: 0 ≤ i ≤ n. Neither the values of i nor n are changed when the step at line 6 is executed, so part (c) of the loop invariant is also satisfied when the loop is reached. Like parts (a) an (b), part (d) is also included in the loop invariant for the outer loop. Since the array R and the values of i and m have not been changed by the execution of the step at line 6, this part of the loop invariant is also satisfied when the inner loop is reached. Part (e) is satisfied because the integer variable j has been declared, with value 0 ≤ m + 1, immediately before the inner loop is reached. Part (f) is satisfied because it is a vacuous (that is, empty) claim, because there are no integers ℓ such that 0 ≤≤≤ j− 1 because j = 0 at this point. Thus the proposed loop invariant for the inner loop is satisfied whenever this loop is reached. Now consider an execution of the body of the inner loop that starts with the proposed loop invariant initially satisfied. None of the steps in the inner loop body (at lines 8–11 change the values of the inputs n and m. Thus, since part (a) of the proposed loop invariant holds then this execution of the loop body begins, it also holds when this execution of the loop body ends. None of the steps in the inner loop body change the type or dimension of the array R, so part (b) is also satisfied at the end of an execution of the loop body if it was satisfied at the beginning of it. This is also true of part (c) because the values of i and n are not changed by any of the statements in the inner loop body, either. While some of the values in the array R are changed by these steps, one can see by an inspection of the steps at lines 9 and 10 that the only entries changed are entries R[i][ℓ] for integers ℓ — and part (d) of the proposed loop invariant only concern entries R[k][ℓ] where 0 ≤ k ≤ i − 1. Thus part (d) of the proposed loop invariant is satisfied at the end of the execution of the inner loop body if it was satisfied at the beginning of it, too. Since part (e) of the proposed loop body is satisfied when the execution of the inner loop body begins, j is an integer variable such that 0 ≤ j ≤ m + 1. Furthermore, since the 8 test at line 7 must have been checked and passed, j ≤ m. While steps 10 and 11 do not change either j or m, step 11 increases the value of j by one without changing m — so that 1 ≤ j ≤ m+ 1 when the bottom of the body of the loop body is reached, as needed to re-establish part (e). Since part (f) is initially satisfied, R[i][ℓ] = Routes(i, ℓ) for every integer ℓ such that 0 ≤ ℓ ≤ j− 1 at the beginning of this execution of the body of the inner loop. Consider the execution of the steps at lines 8–10: • If i = 0 or j = 0 then the test at line 8 is passed and R[i][j] is set to have value 1 = Routes(i,j) at line 9— so that R[i][ℓ] = Routes(i, ℓ) for every integer ℓ such that 0 ≤ ℓ ≤ j at this point. • If i,j ≥ 1 then the test at line 8 is failed and the step at line 10 is executed instead. After the execution of this step, R[i][j] = R[i− 1][j] + R[i][j− 1] (by inspection of this step) = Routes(i− 1,j) + R[i][j− 1] (by part (d) of the loop invariant) = Routes(i− 1,j) + Routes(i,j− 1) (since part (f) is initially satisfied) = Routes(i,j) (since i,j ≥ 1). Thus R[i][ℓ] = Routes(i, ℓ) for every integer ℓ such that 0 ≤ ℓ ≤ j in this case too. The only step remaining in the inner loop body is the step at line 11, which increments the value of j. Since the value is only increased by one, R[i][ℓ] = Routes(i, ℓ) for every integer ℓ such that 0 ≤ ℓ ≤ j − 1 when the bottom of the loop body is reached, and part (f) is also satisfied at this point. Thus, if the loop body is satisfied at the beginning of an execution of the body of the inner loop then it is satisfied at the
end of the execution of the body of the inner loop too. Since the loop test at line 7 has no side-effects it follows by “Loop Theorem #1” that the proposed loop invariant for the inner loop is correct. 7. You were asked to prove that the loop invariant for the outer loop, given above, is also correct. Solution: Consider an execution of this algorithm beginning with the precondition for the “Route Counting” problem satisfied, and consider the state of the computation when the outer loop is first reached. Since the precondition for the problem is satisfied, n and m are integer inputs such that n,m ≥ 0. Furthermore, since the loop has been reached, the test at line 1 must have been checked and failed, so that n,m ≥ 1 — as needed to establish part (a) of the loop invariant. 9 Since the step at line 3 has been executed before the loop has been reached and the array R has not been changed when step 4 is executed, R is an ((n+1)× (m+1)) array of integers, and part (b) is also satisfied when the loop is reached. Part (c) is also satisfied at this point, because i has been set to be an integer variable such that 0 = i ≤ n+ 1 when the step at line 4 is executed. Finally, part (d) is satisfied at this point because the claim is vacuous (that is, empty): There are no integers k such that 0 ≤ k ≤ i− 1 because i = 0 at this point. Thus the proposed loop invariant is satisfied when the loop is first reached. Now consider an execution of the body of the loop that begins with the proposed loop invariant satisfied. Since none of the steps in the loop body change the values of the inputs n and m, part (a) of the loop invariant is satisfied at the end of this execution of the loop body because it was satisfied when this execution of the loop body began. Similarly, none of the statements of the loop body change the type or dimension of the array R, or the values of n or m, part (b) of the loop invariant is also satisfied at the end of an execution of the body of the loop if was satisfied at the beginning of it. Since part (c) of the loop invariant is satisfied at the beginning of the execution of the body of the loop, i is an integer variable such that 0 ≤ i ≤ n + 1. Furthermore, i ≤ n because the loop test at line 5 was checked and passed. While none of the steps in the loop body change the value of n, the value of i is increased by one when the step at line 12 is executed. Thus i is an integer variable such that 1 ≤ i ≤ n + 1 when the bottom of the loop body is reached, establishing part (c). Since part (d) of the loop invariant is satisfied at the beginning of the execution of the loop body, R[k][ℓ] = Routes(k, ℓ) for all integers k and ℓ such that 0 ≤ k ≤ i − 1 and 0 ≤ ℓ ≤ m. After the execution of the steps at line 6 and 7 (which do not change this), the loop at lines 7–11 is reached and executed. There is nothing to prove if the execution of the inner loop does not end, because the bottom of the outer loop body is never reached at all. On the other hand, if the execution of the inner loop terminates then the loop invariant for the inner loop is satisfied when it does, so that R[i][ℓ] = Routes(i, ℓ) for every integer ℓ such that 0 ≤ ℓ ≤ j − 1 — and j is an integer variable such that 0 ≤ j ≤ m + 1. On the other hand, the loop test for the inner loop at line 7 must have been checked and failed, so j > m. Since the values of both j and m are integers it follows that j = m + 1 at this point, so that R[i][ℓ] = Routes(i, ℓ) for every integer ℓ such that 0 ≤ ℓ ≤ m. One can see by inspection of the inner loop that R[k][ℓ] has not been changed for any integers k and ℓ such that 0 ≤ k ≤ i − 1 and 0 ≤ ℓ ≤ m. Thus R[k][ℓ] = Routes(k, ℓ) for all integers k and ℓ such that 0 ≤ k ≤ i and 0 ≤ ℓ ≤ m when the execution of the inner loop ends. One more step, at line 12, is executed before the bottom of the inner loop body is reached. Since this increases the value of i by one, 10 R[k][ℓ] = Routes(k, ℓ) for all integers k and ℓ such that 0 ≤ k ≤ i − 1 and 0 ≤ ℓ ≤ m when the bottom of the inner loop body is reached, so that part (d) of the loop invariant is satisfied. Thus if the loop invariant is satisfied when an execution of the body of the loop begins, then it is satisfied again when (and if) the execution of the body of the loop ends. Since the loop test at line 5 has no side-effects it follows by “Loop Theorem #1” that the loop invariant for the outer loop is correct. 8. You were asked to use this to prove that the algorithm in Figure 2 is partially correct — assuming that the process used above actually works: That is, you may assume that the loop invariant for the outer loop is always satisfied, at the beginning of an execution of the loop body, when you are proving the correctness of a loop invariant for the inner loop.1 Solution: Consider an execution of the algorithm in Figure 2 that begins with the pre- condition for the “Route Counting” problem satisfied, so that n and m are integer inputs such that n,m ≥ 0. If either n = 0 or m = 0 (or both) then the test at line 1 is passed and the execution of the algorithm ends after the step at line 2, with 1 = Routes(n,m) returned — satisfying the postcondition for the “Route Counting” problem. Otherwise n,m ≥ 1, the test at line 1 fails, the steps at lines 3 and 4 are reached and ex- ecuted, and the loop at lines 5–12 is reached and executed as well. Now, if the execution of this loop never ends then the execution of the algorithm never ends either, and there is nothing more to prove. Otherwise, since the loop invariant for the outer loop is satisfied, i is an integer variable such that 0 ≤ i ≤ n+ 1 when the execution of the loop ends. On the other hand, since the test at line 5 must have been checked and failed i > n and, since the values of both i and n are integers, i = n+ 1. It now follows by part (d) of the loop invariant that R[k][ℓ] = Routes(k, ℓ) for all integers k and ℓ such that 0 ≤ k ≤ n and 0 ≤ ℓ ≤ m. In particular, R[n][m] = Routes(n,m), so that Routes(n,m) is returned as output when the step at line 13 is executed — and the postcondition for the “Route Counting” problem is satisfied when the execution of the algorithm ends. In every case, either the execution of the algorithm ends with the postcondition for the “Route Counting” problem satisfied, or the execution of the algorithm does not end at all. Thus the algorithm is partially correct, as claimed. 9. You were asked to state a bound function for the inner loop for this algorithm and show that your bound function is correct — and then use this to find an upper bound for the 1It is possible to state and prove another “loop theorem”’ concerning nested loops implying that this really does work. 11 number of numbered steps included in an execution of the inner loop. (This upper bound might be a function of n, m and i). Solution: Consider the function f(n,m,i,j) = m− j+ 1. Since the inputs n and m and the variables i and j are all defined before the inner loop is reached, and since these all have integer values, f is a well-defined integer-valued function. While an execution of the inner loop body does not change the value of m, the value of j is increased by one because the step at line 11 is always reached and executed. Thus the value of the function f is always decreased by (at least) one when the inner loop body is executed. Suppose that f(n,m,i,j) ≤ 0, that is, m− j+1 ≤ 0. Then j ≥ m+1, so that j > m and the loop test at line 7 would fail if checked, causing the inner loop to halt. Since all the conditions in the definition for a “bound function for a while loop” are satisfied, it follows that f is a bound function for the inner while loop in this algorithm. Since the inner loop body consists of a simple test and a fixed number of other steps (with no other methods being called) each execution of the inner loop body halts. Since the loop test at line 7 has no side-effects it follows by “Loop Theorem #2” that each execution of the inner loop b
ody (included in an execution of the algorithm, starting with the problem’s precondition satisfied) halts. Furthermore, since j initially has value 0, the initial value of f is m+1. There are at most m+ 1 executions fo the body of the loop (in any execution of the loop) and at most m+ 2 executions of the loop test. Each execution of the loop body includes the execution of three statements (either at lines 8, 9 and 11 or at lines 8, 10 and 11), while each execution of the loop test includes a single step. It follows that the number of steps included in an execution of the inner loop is at most m+1∑ k=1 3 + m+2∑ k=1 1 = 3(m+ 1) + (m+ 2) = 4m+ 5. 10. You were asked to state a bound function for the outer loop for this algorithm and show that your bound function is correct — and then use this to find an upper bound for the number of numbered steps included in an execution of the outer loop. (This upper bound might be a function of n and m). Solution: Consider the function g(n,m,i) = n− i+ 1. 12 Since the inputs n and m and the variable i are all defined before the inner loop is reached, and since these all have integer values, f is a well-defined integer-valued func- tion. While an execution of the inner loop body does not change the value of n, the value of i is increased by one because the step at line 12 is always reached and executed. Thus the value of the function g is always decreased by (at least) one when the inner loop body is executed. Suppose that g(n,m,i) ≤ 0, that is, n − i + 1 ≤ 0. Then i ≥ n + 1, so that i > n and the loop test at line 5 would fail if checked, causing the outer loop to halt. Since all the conditions in the definition for a “bound function for a while loop” are satisfied, it follows that g is a bound function for the outer while loop in this algorithm. Since the outer loop body consists of the inner loop and two additional steps, neither of which call other methods, and since an execution of the inner loop (that is part of an execution of the algorithm starting with the problem’s precondition satisfied) has been proved to terminate, each execution of the outer loop body (that is also part of an execu- tion of the algorithm with the problem’s precondition satisfied) halts. Since an execution of the outer loop test also always halts and the outer loop test has no side-effects, it follows that every execution of the outer loop is guaranteed. Furthermore, since i has initial value 0, g has initial value n + 1, so that there are at most n+ 1 executions of the body of the outer loop and at most n+ 2 executions of the outer loop test. It follows by the results of the previous question that each execution of the inner loop body uses at most 4m + 7 steps, while each execution of the outer loop test uses a single step. The total number of steps included in execution of the outer loop is, therefore, at most n+1∑ k=1 (4m+ 7) + n+2∑ k=1 1 = (n+ 1)(4m + 7) + (n+ 2) = 4nm+ 7n+ 4m+ 7 + n+ 2 = 4n+ 8n+ 4m+ 9. 11. You were asked to complete a proof that if the algorithm in Figure 2 is executed with non-negative integers n and m given as input (so that the precondition for the the “Route Counting” problem is satisfied) then the execution of the algorithm terminates — and give an upper bound, depending on n and m, for the number of numbered steps included in this execution of the algorithm. Solution: Consider an execution of the algorithm in Figure 2 with non-negative inte- gers n and m as inputs. If n = 0 or m = 0 then the test at line 1 is checked and the execution of the algorithm ends with the step at line 2. Two numbered steps have been executed. 13 Otherwise the test at line 1 is checked and fails. Steps 3 and 4 are executed before the outer while loop is reached and executed. It follows by the results of the previous question that this execution of the algorithm terminates after at most 4nm+8n+4m+ 9 steps are executed. One more step (at line 13) is executed after that, so that at most 4nm+ 8n+ 4m+ 13 steps are executed. It follows that the total number of numbered steps executed, on inputs n,m ≥ 0, is at most TRoutes2(n,m) = { 2 if n = 0 or m = 0, 4nm+ 8n+ 4m+ 13 if n,m ≥ 1. 12. You were asked to write another program, “Routes2,” to compute Routes(n,m) as well. This was to resemble the program “Routes1” but was to include an implementation of the algorithm in Figure 2 instead of the algorithm in Figure 1. Solution: A Java program Routes2.java that meets these requirements is now avail- able. 14 欢迎咨询51作业君
