CSDS 454/340 Assignment 1 PDF

Preview

Summary

Assignment 1...

Description

Assignment 1 Le Leii Ruan Student IID D:34588 3458846 46

Pro rob bl em 1 (1 (1)) [A [Ans ns nswe we werr] x = m ∗ GCD(a, b) , where m, n ∈ ℤ+ . The loop terminates Loop Invariant: at the beginning of each loop, � ฀ ฀ = n ∗ GCD(a, b) when x’=y’. (2 (2)) [Ans nswe we werr] i.

[Initiation] At the beginning of the first loop, x = a, y = b. According to the definition of GCD, exist a 0, ฀฀0 ∈ x = a 0 ∗ GCD(a, b) , which satisfies the loop invariant. ℤ+ , such that � ฀ ฀ = b0 ∗ GCD(a, b)

ii.

[Maintenance] Assume that at the beginning of the loop with x = x ′ , y = y′ , exist m′, n′ ∈ ℤ+ , such that �

x′ = m′ ∗ GCD(a, b) . We need to prove that the loop invariant stays true at the beginning of the ฀฀′ = n′ ∗ GCD(a, b)

next loop.

a) If x ′ = y′, the loop terminates, which returns x′ as GCD(a, b). (to be proved later) x ← x ′ − y ′ = (m′ − n′) ∗ GCD(a, b) , where (m′ − n′), ฀฀′ ∈ ℤ+ , which keeps the ฀฀ ← y ′ = n′ ∗ GCD(a, b) loop invariant.

b) If x ′ < y′ , �

c) If x ′ > y′, �

x ← x ′ = m′ ∗ GCD(a, b) , where (n′ − m′), ฀฀′ ∈ ℤ+ , which keeps the ฀฀ ← y ′ − x ′ = (n′ − m′) ∗ GCD(a, b)

loop invariant. (3 (3)) [Ans nswe we werr] x′ = m′ ∗ GCD(a, b) , we have x ′ + y ′ = (m′ + n′) ∗ GCD. At the beginning of the loop where � ฀฀′ = n′ ∗ GCD(a, b) a) If x ′ = y′, the loop terminates, which returns x′ as GCD(a, b). (to be proved later) b) If x ′ < y′, �

x ← x ′ − y ′ = (m′ − n′) ∗ GCD(a, b) , where (m′ − n′) + ฀฀ ′ = ฀฀ ′ < ฀฀ ′ + ฀฀′. ฀฀ ← y ′ = n′ ∗ GCD(a, b)

c) If x ′ > y′, �

x ← x ′ = m′ ∗ GCD(a, b) , where (n′ − m′ ) + ฀฀ ′ = ฀฀ ′ < ฀฀ ′ + ฀฀′. ฀฀ ← y ′ − x ′ = (n′ − m′) ∗ GCD(a, b)

Accordingly, (m’ + n’) decreases during each loop. And since it is stated in the loop invariant that m′, n′ ∈ ℤ+ , it’s obvious that m′ + n′ ≥ 2. When m′ + n′ > 2, if the loop terminates, we’ll return GCD(a,b)= x ′ = y ′ = m ∗ GCD(a, b) > GCD(a. b). which leads to contradiction. So the loop will not terminate until m′ + n′ decreases to 2, i.e. the final state must be m′ = n′ = 1.

(4 (4)) [Answ swe er] According to the loop invariant, the loop terminates when x = y. i. e. m = n and returns x = m ∗ GCD(a, b).. If when loop terminates, m>1. Then we could prove that all the former x and y could be divided by m*GCD(a,b), also for a and b. Thus according to the definition of GCD, we’ll end up with GCD(a,b)=m*GCD(a,b)>GCD(a,b), which leads to contradiction. So when the loop terminates, m must be 1, and the value we return must be x=GCD(a,b).

Pr Pro o blem 2 (1 (1)) [A [Ans ns nswe we werr] FIND_IJ (A, B, n, x) i ← 1, j ← n while (i ≤ n) and (j ≥ 1) if A[i]+B[j] equals to x return i, j elseif A[i]+B[j>x j ← j−1 else i←i+1 endwhile return FALSE (2 (2)) [Answ swe er] i.

Initiation:

ii.

At the beginning of the loop where i = i′ ฀฀฀฀฀฀ ฀ ฀ = ฀฀′ If i′ = n + 1 or j′ = 0, the loop terminates and return FALSE.

Else if A[i]+B[j]>x, j decrements.

If A[i]+B[j]x, we need to prove the loop invariant keeps for i=i’ and j=j’-1, i.e. there’ll be no solution in the subarray of A[1…i’] and B[(j’-1]+1…n]. According to the assumption, there’ll be no solution in the subarray of A[i’+1…n], thus for ∀i < i′, A[i] + B[j′] ≠ x. Besides, since the array A[1…n] is monotonically increasing, for ∀i ≥ i′ , we have A[฀฀] + B[j′] ≥ A[i′] + B[j′] > x. Concluding, for ∀i ∈ [1 … n], we have A[i′] + B[j] ≠ x , which proves that B[j’] is not the solution and there’ll be no solution in the subarray of A[1…(i’+1)-1] and B[j’+1…n]. c) Termination Case I: If the loop terminates by i=n+1, at the beginning of that loop, there’s no solution in the subarray of A[1…n+1-1], which indicates that there’s no solution in the whole array A. Here we return FALSE. Case II: If the loop terminates by j=0, at the beginning of that loop, there’s no solution in the subarray of B[0+1….n], which indicates that there’s no solution in the whole array B. Here we return FALSE. Case III: If the loop terminates by A[i]+B[j]=x, we return i and j as solution. Since we don’t consider multiple solutions in this case, this is the result we need. d) Why Terminates In each loop, either i will increment or j will decrement. Since there’s one termination condition of i=n+1 or j=0, the loop will terminate within 2n steps. (4 (4)) [Ans nswe we werr] For the worst case, the loop will not terminate until i=n+1 or j=0, and the maximum number of steps will be 2*n-1. Besides, in each loop, the operation has constant runtime, and the operations outside the loop has constant runtime. Thus the worst case runtime will be θ(n)

Pr Pro o blem 3 (1) Concl clu usio ion n Pisidians, if n mod 2 ≡ 1 The species will be � . Lydians, if n mod 2 ≡ 0

(2) Loo p Inv nva ariant

Suppose the number of Pisidians is p and the number of Lydians is l. At the beginning of the kth loop, l+p=m+n-k+1, and p mod 2≡ n mod 2. The loop terminates when l+p=1. (3) Proof i.

Initiation At the beginning of the first loop, l=m, p=n, which naturally satisfies l+p=m+n and p mod 2≡n mod 2.

ii.

Maintenance Assume that at the beginning of the k’ th loop, we have l’+p ’=m+n and p’ mod 2 ≡n mod 2. We need to prove the loop invariant keeps at the beginning of the (k’+1)th loop. Case I: if l’+p’=1, i.e. k’=1, terminates. Case II: if 2 Lydians fight, we have l′ ← l′ − 1. p′ ← p′. We have (l’ − 1) + p′ = m + n − (k + 1) + 1 for k ′ ← k ′ + 1 , and since p’ doesn’t change, we naturally keeps p’ mod 2≡ n mod 2. Case III: if 2 Pisidians fight, we have l′ ← l′ + 1, p′ ← p′ − 2 We have (l’ + 1) + (p′ − 2) = m + n − (k + 1) + 1 for k ′ ← k ′ + 1 , and (p’ − 2) mod 2 ≡ p’ mod 2 ≡ n mod 2. Case IV: if one Lydians fight with one Pisidians, we have l′ ← l′ − 1. p′ ← p′

We have (l’ − 1) + p′ = m + n − (k + 1) + 1 for k′ ← k ′ + 1, and since p’ doesn’t change, we naturally keeps p’ mod 2≡ n mod 2.

(4) Termination When the loop terminates, i.e. p+l=1. Case I: p=1, l=0. The Pysidian will exist, and in this case we have n mod 2≡ l mod 2 ≡ 0 Case 2: p=0, l=1. The Lydians will exist, and in this case we have n mod 2≡ l mod 2 ≡ 1 (5) Wh Why y ter ermin min minat at ates es since k starts from 1 and keeps incrementing, within finite steps we must have k=m+n when l+p=m+n-k+1=1 and the loop terminates....