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

E.? :(

---

I couldn't find this online either - does a loop invariant not hold if it is an infinite loop?

---

Hmm same doubt! Arjun sir please help!

---

check the answer given by MK

---

We use loop invariants to help us understand why an algorithm is correct. We must show three things about a loop invariant:

Initialization: It is true prior to the first iteration of the loop.

Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.

Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Source: CLRS.

---

They have used "must"

---

Yes my answer is wrong termination is must but at wiki i didn't found the termination part or maybe i skipped it :(

---

Nope. Don't know what's correct but I remembered this termination part in the exam. No idea what's the correct answer.

---

Means in loop invariant we need to check loop working properly or not

right?

Here  mistake in coding itself,

So, no need to check other conditions

---

srestha after termination we need to check the invariant too but it never terminates so we can't check, that's why $E$ seems appropriate

---

@Mk Utkarsh

if u know nothing about invarient and just run the pseudocode

u can see $y<x$ proceeds to an infinite loop

So, can we conclude that loop invariant is nothing but, the ioop working properly or not?

---

@Mk Utkarsh

Same mistake I have done in programming question :(

---

srestha which question?

---

ans 120 that one :/

---

ohh :( :|

---

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?