1. (a) Consider the following algorithm: Input: A number k 20 Output: ?? X +0 Y +1 while x k do X + x+1 Y +Y * X return Y i. Give the output of this algorithm in terms of the input. ii. Write a loop...

part a iii

Extracted text: 1. (a) Consider the following algorithm: Input: A number k 20 Output: ?? X +0 Y +1 while x k do X + x+1 Y +Y * X return Y i. Give the output of this algorithm in terms of the input. ii. Write a loop invariant for this algorithm. iii. State and use the While-loop invariance theorem to prove that this algorithm is correct with respect to the output you gave in Part i. iv. Rewrite the algorithm using a For-loop rather than a While-loop. (b) Derive the following judgement using natural deduction: A implies (B and C), B implies D, C implies E- A implies (D andE) State clearly all the rules that you use in your derivation.