FE (CS) Batch 2022 HW
CS-211
Homework (Solution)
Topic(s) Proving Loop Invariant via Mathematical Induction
Use mathematical induction to establish truth of loop invariant in each of the following cases. Also, use termination
condition of while loop along with the loop invariant to prove that each of the following functions computes the intended
output.
A.
FUNCTION COMP(X,Y;Z)
1. Z ← X
2. W ← Y
3. WHILE (W > 0)
a) Z ← Z + Y
b) W ← W – 1
4. RETURN (Z)
END OF FUNCTION COMP
Computes: Z = X + Y2
Loop Invariant: (Y * Wn) + Zn = X + Y2
Proving base case
P(0): (Y * W0) + Z0 = X + Y2
⇒ (Y * Y) + X = X + Y2
⇒ X + Y2 = X + Y2
Hence, base case P(0) holds.
Inductive Hypothesis P(k)
(Y * Wk) + Zk = X + Y2 --------------- (I.H.)
Let’s check P(k + 1)
(Y * Wk + 1) + Zk + 1
= (Y * (Wk – 1)) + Zk + Y (From body of loop)
= (Y * Wk – Y) + Zk + Y
= (Y * Wk) + Zk
= X + Y2 (From I. H.)
Thus, P(k) → P(k + 1). This shows that the expression (Y * Wn) + Zn = X + Y2 is loop invariant for the given loop.
Loop Termination
Loop terminates when W = 0, in which case the loop invariant yields: (Y * 0) + Z = X + Y2 ⇒ Z = X + Y2
Page 1 of 4
FE (CS) Batch 2022 HW
CS-211
B.
FUNCTION DIFF(X,Y;Z)
1. Z ← X
2. W ← Y
3. WHILE (W > 0) {
a) Z ← Z – 1
b) W ← W – 1
}
4. RETURN (Z)
END OF FUNCTION DIFF
Computes: Z = X – Y
Loop Invariant: Zn = X – Y + Wn
Proving base case
P(0): Z0 = X – Y + W0
⇒ X=X–Y+Y
⇒ X=X
Hence, base case P(0) holds.
Inductive Hypothesis P(k)
Zk = X – Y + Wk --------------- (I.H.)
Let’s check P(k + 1)
Zk + 1 = X – Y + Wk + 1
= Zk – 1 = X – Y + Wk – 1 (From body of loop)
= Zk = X – Y + Wk
Thus, P(k) → P(k + 1). This shows that the expression Zn = X – Y + Wn is loop invariant for the given loop.
Loop Termination
Loop terminates when W = 0, in which case the loop invariant yields: Z = X – Y + 0 ⇒ Z = X – Y
C.
FUNCTION EXP2(N,M;R)
1. R ← 1
2. K ← 2M
3. WHILE (K > 0)
a) R ← R x N
b) K ← K – 1
4. RETURN (R)
END OF FUNCTION EXP2
Computes: R = 𝑁 2𝑀
Loop Invariant: Rn x 𝑁𝑘𝑛 = 𝑁 2𝑀
Page 2 of 4
FE (CS) Batch 2022 HW
CS-211
Loop Invariant: Rn x 𝑁𝑘𝑛 = 𝑁 2𝑀
Proving base case
P(0): R0 x 𝑁𝑘0 = 𝑁 2𝑀
⇒ 1 x 𝑁 2𝑀 = 𝑁 2𝑀
⇒ 𝑁 2𝑀 = 𝑁 2𝑀
Hence, base case P(0) holds.
Inductive Hypothesis P(L)
RL x 𝑁𝑘𝐿 = 𝑁 2𝑀 --------------- (I.H.)
Let’s check P(L + 1)
RL + 1 x 𝑁𝑘𝐿+1
= RL * N x 𝑁𝑘𝐿 −1 (From body of loop)
= RL x 𝑁𝑘𝐿
Thus, P(L) → P(L + 1). This shows that the expression Rn x 𝑁𝑘𝑛 = 𝑁 2𝑀 is loop invariant for the given loop.
Loop Termination
Loop terminates when k = 0, in which case the loop invariant yields: Rn = 𝑁 2𝑀
D.
FUNCTION SQS(X,Y;Z)
1. Z ← Y
2. W ← X
3. WHILE (W > 0)
a) Z ← Z + X
b) W ← W – 1
4. W ← Y – 1
5. WHILE (W > 0)
a) Z ← Z + Y
b) W ← W – 1
6. RETURN (Z)
END OF FUNCTION SQS
Computes: Z = X2 + Y2
Loop Invariant (First Loop):
Zn + (X * Wn) = Y + X2
Loop Invariant (Second Loop):
Zn + (Y x Wn) = X2 + Y2
Page 3 of 4
FE (CS) Batch 2022 HW
CS-211
1st Loop Invariant: Zn + (X * Wn) = Y + X2
Proving base case
P(0): Z0 + (X * W0) = Y + X2
⇒ Y + (X * X) = Y + X2
⇒ Y + X2 = Y + X2
Hence, base case P(0) holds.
Inductive Hypothesis P(k)
Zk + (X * Wk) = Y + X2 --------------- (I.H.)
Let’s check P(k + 1)
Zk + 1 + (X * Wk + 1)
= Zk + X + (X * (Wk – 1)) (From body of loop)
= Zk + (X * Wk)
Thus, P(k) → P(k + 1). This shows that the expression Zn + (X * Wn) = Y + X2 is loop invariant for the 1st loop.
Loop Termination
Loop terminates when W = 0, in which case the loop invariant yields: Z + (X * 0) = Y + X2 ⇒ Z = Y + X2
2nd Loop Invariant: Zn + (Y x Wn) = X2 + Y2
Proving base case
The value of Z obtained from termination of 1st loop will be used as initial value of Z for 2nd loop.
P(0): Z0 + (Y x W0) = X2 + Y2
⇒ Y + X2 + (Y x (Y – 1)) = X2 + Y2
⇒ X2 + Y2 = X2 + Y2
Hence, base case P(0) holds.
Inductive Hypothesis P(k)
Zk + (Y x Wk) = X2 + Y2 --------------- (I.H.)
Let’s check P(k + 1)
Zk + 1 + (Y x Wk + 1)
= Zk + Y + (Y * (Wk – 1)) (From body of loop)
= Zk + (Y * Wk)
Thus, P(k) → P(k + 1). This shows that the expression Zn + (Y x Wn) = X2 + Y2 is loop invariant for the 2nd loop.
Loop Termination
Loop terminates when W = 0, in which case the loop invariant yields: Z + (Y * 0) = X2 + Y2 ⇒ Z = X2 + Y2
Page 4 of 4
