Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 2080 Winter 2022 Homework Assignment 2

SOLUTIONS


Some notation we’ll be using concerning an array A in some parts of this assignment:

● The value of A.length correctly represents the number of elements in array A.

● The array indices are 0 up to A.length 一 1.

● The notation A[i] represents the element at index i in A.

● For any integers y ≥ x, the subarray notation A[x . . . y] represents an array B of length y 一 x + 1 such that:

B[i] = A[x + i] for each i e {0, . . . , y 一 x)

Some examples: Suppose A = [2, 4, 6], then A[0 . . . 0] = [2] and A[1 . . . 2] = [4, 6]

● For any integers y < x, the subarray notation A[x . . . y] represents an empty array, i.e., it contains no elements.


Assignment questions start here:

1.  For both parts of this question, consult Algorithm 1. Your answers should follow the same style and format as shown in the Algorithm Correctness lectures 2, 3, 4.


Algorithm 1

1:

//pre: (y == 11) A (n e {9, 16)

2:

x - 3

3:

z - x + y

4:

//assert:

5:

if n is odd then

6:

z - z/2

7:

end if

8:

//post: z == n 2


(2 pts)          (a)  Provide an assert statement for line 4. You’ll need to do some planning ahead: read part (b)

to help guide your choice for the assert statement.


Solution

On Line 4, define assert as (z == 14) A (n e {9, 16)


(6 pts)          (b) Write out your assert statement from part (a) again, then prove that the code satisfies the

Partial Correctness property. In particular: your solution should consist of two proofs, one for each of the following statements:

(1)  ((pre is true at line 1) A (line 4 is reached)) → (assert is true when line 4 is reached)

(2)  ((assert is true at line 4) A (line 8 is reached)) → (post is true when line 8 is reached) Note: If you are having trouble proving either of the two statements above, you might need to go back to part (a) and change your assert statement. Also, make sure your proof that post is true does not rely on any information that appears before line 4 (again, you might need to adjust your assert statement to prevent this).


Solution

On Line 4, define assert as (z == 14) A (n e {9, 16)

Proof.

(1)  First, we prove the statement

((pre is true at line 1) A (line 4 is reached)) → (assert is true when line 4 is reached)

(2)  Suppose that the following statement is true:

(pre is true at line 1) A (line 4 is reached).

(3)  Then the following statement is true: pre is true at line 1. In particular, this means that y = 11 and n e {9, 16)at line 1.

(4)  From (3) and the fact that the value of y is not modified in line 2 of the code, it follows that y = 11 when line 3 is reached.

(5) At line 2, variable x is set to 3, so the value of x is 3 immediately before line 3.

(6)  From (4) and (5), we conclude that x + y = 11 + 3 = 14. This value is assigned to z on line 3, so the value of z is 14 immediately before line 4.

(7)  From (3) and the fact that the value of n is not modified in lines 2-3 of the code, it follows that n e {9, 16)immediately before line 4.

(8)  From (6) and (7), we see that z is equal to 14 and n e {9, 16)at line 4, which confirms that our assert is true when line 4 is reached.

(9)  Next, we prove that

((assert is true at line 4) A (line 8 is reached)) → (post is true when line 8 is reached)

(10)  Suppose that the following statement is true:

(assert is true at line 4) A (line 8 is reached).

(11)  Then the following statement is true: (assert is true at line 4). In particular, this means that z = 14 and n e {9, 16).

(12)  There are two cases to consider based on the possible values of n:


● Case (a): suppose that n = 9. In this case, since n is odd, the if condition on line 5 evaluates to true. This means that line 6 is executed. From (11), we know that z = 14 at line 4, and, since the value of z is not changed on line 5, the value of z is   14 immediately before line 6. At line 6, the value of z is changed to z/2 = 14/2 = 7, so, immediately after line 6, the value of z is 7. As the value of z is not changed after line 6, the code reaches line 8with z = 7 = 9 一 2 = n 一 2. This proves that post is   true when line 8 is reached.

● Case (b): suppose that n = 16. In this case, since n is even, the if condition on line 5 evaluates to false. This means that line 6 is not executed, and line 8 is reached      immediately after line 5. From (11), we know that z = 14 at line 4, and, since the   value of z is not changed on line 5, it follows that z = 14 = 16 一 2 = n 一 2 at line 8. This proves that post is true when line 8 is reached.

n








































3


(6 pts)    2.  Using strong induction, prove that the following recursive program is fully correct.  Your answer

should follow the same style and format as shown in the Algorithm Correctness lecture 7.



Algorithm 2 int FindMinRec(A)

1:

//pre: (A is an array of integers) A (A.length 1)

2:

if A.length == 1 then

3:

returnVal - A[0]

4:

else

5:

recurseMin - FindMinRec(A[1 . . . (A.length 1)])

6:

if A[0] recurseMin then

7:

returnVal - A[0]

8:

else

9:

returnVal - recurseMin

10:

end if

11:

end if

12:

return returnVal

13:

//post: (the returned value is the minimum value among all elements in A)


Solution

Proof.

(1)  Let P(n) be the predicate:

for every array A of size n, if pre is true, then FindMinRec(A) terminates and returns the minimum value among all elements in A

(2) We prove that the predicate P(n) is true for all n ≥ 1, by strong induction on n.

(3) Base Case:

(4)  Consider n = 1, and consider an arbitrary array A of size 1.

(5) At line 2 of the code, the if condition evaluates to true, so line 3 is executed next.

(6) At line 3, the value of returnVal is set to A[0], and line 12 is executed next.

(7) At line 12, the value of returnVal is returned (and the function terminates), so A[0] is returned. Note that A[0] is the only element in the array since the array has size 1, so A[0] is the minimum value among all elements in A. This concludes the proof of P(1).

(8) Induction Hypothesis: Assume, for some n ≥ 2, that P(1) A...A P(n 1) is true.

(9) Inductive Step: We prove that P(n) is true.

(10)  Let A be an arbitrary array of size n ≥ 2.

(11) As n ≥ 2, the if condition at line 2 evaluates to false, so line 5 is executed next.


(12)  On line 5, the function FindMinRec is called with parameter A[1 . . . (A.length 1)],  which is an array of integers of size (A.length 一 1) 一 1 + 1 = A.length 一 1 = n 一 1. Since n ≥ 2, we know n 一 1 ≥ 1. By the Induction Hypothesis, P(n 一 1) is true, and since the precondition holds, the call to FindMinRec terminates and returns the minimum value among all             elements in A[1 . . . (A.length 一 1)]. This value is stored in the variable recurseMin at line 5, and the value of recurseMin is not changed in any future lines.

(13) At line 6, we separately consider two possible cases, depending on whether or not the if condition evaluates to true.

(14)  Case 1: the if condition on line 6 evaluates to true. Then line 7 is executed, which sets returnVal to A[0]. Line 12 is executed next, so A[0] is returned and the function     terminates.

The fact that the if condition evaluated to true means that elementA[0] ≤ recurseMin.     But, by (12), the value of recurseMin is the minimum value among all elements at indices 1, . . . , (A.length 1). This means there is no smaller element than A[0] in the entire array.

Therefore, the returned value is the minimum value among all elements in A, which concludes the proof of the inductive step for Case 1.

(15)  Case 2: the if condition on line 6 evaluates to false. Then line 9 is executed, which  sets returnVal to recurseMin. Line 12 is executed next, so recurseMin is returned and the function terminates.

The fact that the if condition evaluated to false means that elementA[0] > recurseMin.     But, by (12), the value of recurseMin is the minimum value among all elements at indices 1, . . . , (A.length 1), and we know that A[0] is larger. Therefore, the returned value is the     minimum value among all elements in A, which concludes the proof of the inductive step for

Case 2.

n