TIFR CSE 2010 | Part B | Question: 37

Question

Consider the program where $a, b$ are integers with $b > 0$.

x:=a; y:=b; z:=0;   
while y > 0 do
    if odd (x) then
        z:= z + x;
        y:= y - 1;
    else y:= y % 2;
        x:= 2 * x;
    fi

Invariant of the loop is a condition which is true before and after every iteration of the loop. In the above program the loop invariant is given by

              $0\leq y$ and $z + x * y= a * b$

Which of the following is true of the program?

• A. The program will not terminate for some values of $a, b$.
• B. The program will terminate with $z=2^{b}$
• C. The program will terminate with $z = a * b$.
• D. The program will not terminate for some values of $a, b$ but when it does terminate, the condition $z = a * b$ will hold.
• E. The program will terminate with $z=a^{b}$

Comments

by counter example like for a= 2 and b =1 the loop does not terminate thus remaining options are A and D.
But I'm having problem getting D as answer my answer is A as at any random example say a = 4 and b =2  we get final values as x = 8 and y = 0 and z = 0 and evidently  z != a*b , so I go with Option A.

Please correct me if I'm wrong.

---

the answer should be A option. Take any example of both A and B even no
ex-  a=10 b=2
correct the answer !!!!!!

Answer 1

if $x$ is odd then -

• $z =a*b$ will be the o/p

if $x$ is even then -   

case 1: if $y$ is even then $x =2*x$ and $z=0$ will be o/p 

case 2: $y$ is odd then loop will not terminate .

EDIT - When x and y are even, for some values of x, condition z= ab is not holding.
For example - when $a=4 \  and  \ b = 4,$ after loop terminates, $z= 8 \ and \ ab = 16.$
$8 \neq 16.$
So, A should be the correct answer.  

Comments

Wrong solution program terminates for a = 5 and b = 1 so option d is correct @admin please correct the solution

---

Nope, when you take a=b=x=y=2

It terminates but z = ab doesnt hold. A is correct here.

---

How come $0 <= y$ is a loop invariant?

Answer 2

Option D is correct.

Four possible cases arise here:

1. x = EVEN, y = EVEN

2. x = ODD, y = ODD

3. x = ODD, y = EVEN

4. x = EVEN, y = ODD

Case 1:

x is even, so else part will be executed.

x = 2x, y = 0, z = 0 (z = x*y = a*b)

Case 2:

x is odd, so if part is executed.

After 1st iteration --> x = no change, y reduces by 1, z increases by 1.x.

After 2nd iteration --> x = no change, y = reduces by 2 from the original value, z increase by 2.x (value of x used before the loop).

Here x doesn't change, so the loop will never execute the else part of the code.

The loop will stop only when y becomes 0. As you can see y decreases by 1 every iteration, so final values will be

x = no change, y becomes 0, z = x added y no. of times (i.e z = x*y = a*b).

Case 3:

Same as case 2 where x is odd, so only if part of the code will be executed for every iteration.

The loop will stop when y becomes 0, so the final values will be

x = no change, y becomes 0, z = x added y no. of times (i.e z = x*y =  a*b).

Case 4:

x is even, so for the first iteration, else part will be executed which leads to

x = 2x, y = 1 (odd % 2 = 1), z = 0.

The loop will never end because y > 0 throughout the loop at every iteration.

So for some values of a & b, the loop will never terminate, but if it terminates then z = a*b will hold.

Comments

Dear @rfzahid I think there is a flaw in your solution in case-1 you have written in the last line that z=x*y=a*b is not right as in option we have given as z=a*b, the value of x and y in not constant (changing) during program execution whereas the value of a & b remains constant throughout the program execution. Suppose a=8(Even)  and b=2(Even) then value of z remains 0 as we are not updating value of z in else part but a*b= 8*2=16 whereas x*y= (Even*0) =0. So, you can't claim that z=x*y=a*b.

Hence option A is right option in my view.

Please correct me if I am wrong.

Answer 3

Option D should be right coz for X= even and Y=odd ,the program doesn't terminate

, For X=Y=even when it terminate the value of Z = a * b.