TIFR CSE 2019 | Part B | Question: 9

Question

Consider the following program fragment:

var x, y: integer;
x := 1; y := 0;
while y < x do
begin
   x := 2*x;
   y := y+1
end;

For the above fragment , which of the following is a loop invariant ?

• A. $x=y+1$
• B. $x=(y+1)^2$
• C. $x=(y+1)2^y$
• D. $x=2^y$
• E. None of the above, since the loop does not terminate

Comments

check comment on my answer @Utkarsh @srestha @Shaik Masthan

---

Loop invariant has to hold truth value true, before and after a loop

There are some initial conditions, which make this happen possible

---

Loop invariant is which doesn't change after  a loop  it remains same after the loop is executed or before the loop is executed.

The option  x=2power y

remains constant throughout

x=1 y=0  that is 1 = 2 power 0

x=2 y=1  then 2=  2 power 1 where y=1

x=4 y=2  then 2=  2 power 2 where y=2

 This remains constant that is the condition of loop  invariant  

SO option D is correct

 

Find the respective option here in TIFR  2019 computer science paper

http://univ.tifr.res.in/gs2021/Files/GS2019_QP_CS.pdf

Answer 1

A loop invariant is any condition which is true for the start of the loop, for every iteration of the loop and for the exit of the loop.

Before 1st iterations values of $(x,y)$ are $(1,0)$

After 1st iteration values of $x$ and $y$ are $(2,1)$

After 2nd iteration values of $x$ and $y$ are $(4,2)$

After 3rd iteration values of $x$ and $y$ are $(8,3)$

$\vdots$

After nth iteration values of $x$ and $y$ are $(2^n,n)$

This loop will not terminate and that means we need not worry about the condition when loop exits $(p\to q$ is TRUE if $p$ is false) So $E$ is false

$D$ is the right option

Comments

A loop invariant has nothing to do with termination?

---

sir in cormen definition they used loop invariant to show correctness of algorithm but term "loop invariant" has not directly related to termination of algo or loop.

here also for achieving goal we are using loop invariant + termination but even if termination is not there loop invariant will not change, ultimately we can say this algorithm doesn't solve any purpose because loop is not terminating but invariant is same if it terminates or not.

 

@Utkarsh check cormen definition again it uses invariant to show insertion sort algo is correct.

---

idk what is correct :(

---

If anyone is reading these comments, the final answer is D. You can check the answerkey

Answer 2

Best way to solve is by Dry run

See the pattern yourself

 

Comments

So infinite loop has nothing to do with loop invariant? What about the loop termination?