Scribd
Upload
5 views

Loop Invariant Solution

Uploaded by

zainab noor
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views

Loop Invariant Solution

Uploaded by

zainab noor
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

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

You might also like