GATE CSE 2015 Set 1 | Question: 33

Question

Consider the following pseudo code, where $x$ and $y$ are positive integers.

begin 
    q := 0 
    r := x 
   while r ≥ y do 
      begin 
      r := r - y 
      q := q + 1 
    end 
end

The post condition that needs to be satisfied after the program terminates is

• A. $\{ r = qx + y \wedge r < y\}$
• B. $\{ x = qy  + r \wedge r < y\}$
• C. $\{ y = qx + r \wedge 0 < r < y\}$
• D. $\{ q + 1 < r - y \wedge y > 0\}$

Comments

https://gateoverflow.in/118381/gate2017-2-37

---

“ ^ “ is EXOR operator in C language.

take y =2 x= 11 and simply you get option B as answer  

---

Concept in Loop Invariant Problems:

Just take arbitrary values of variables, here x and y as q is already given (0) and perform operations in while loop.

Satisfy the options with the updated values of variables.

 

Answer 1

Correct Option: B

The loop terminates when $r < y$. So, $r < y$ is one post condition. 

In each iteration $q$ is incremented by $1$ and $y$ is subtracted from $r$. Initial value of $r$ is $x$. So, loop iterates $x/y$ times and $q$ will be equal to $x/y$ and $r = x\%y \Rightarrow x = qy + r;$ 

Comments

No that has to be AND but anyhow I don't think there is as such hard and fast rule, as people commonly write according to the convenience.

Only in standard things you will find the right way.

---

^ is EXOR operator in C language. You have to see the context.

---

@Arjun sir      @jeetsir.....ty for ur valuable comment.

Answer 2

Just take an example and try to solve it by using options:

suppose, x=10 and y=5

begin 
    q := 0  // q = 0
    r := x  // r = x i.e. r = 5 as value of taken as 10
   while r ≥ y do  // 10 ≥ 5 ; TRUE     (first iteration)
      begin 
      r := r - y  // r = 10 - 5 = 5
      q := q + 1  // q= 0 + 1 = 1
    end 
   while r ≥ y do // 5 ≥ 5 ; TRUE        (second iteration)
      begin 
      r := r - y // r = 5 - 5 = 0 
      q := q + 1 // q= 1 + 1 = 2
    end 
  while r ≥ y do // 0 ≥ 5 ; FALSE         (third iteration)
end

at the end of while loop

we get value of r = 0 and q = 2

x= 10 and y = 5

Now one by one put these values in given option 

and thus, option B satisfied i.e. 

{x=qy+r∧r<y}   // x = 2*5 + 0 = 10 and 0 < 5

Comments

@rishu_darkshadow

Good explanation

In this type of question, i always solve to assume the value, because I'm not comfortable to solve the question in the variable. 

---

so,nice explanation 

 

post condition :-

the loop terminates when ( r<y ) so one condition { r<y }

( q=q+1 ) q is increasing every time by 1 so q is simply counting loop count.

so r after execution

r = r - q y

(r=x) so

r = x - q y

x = r + q y

so option B

x = r + qy ^ r < y

Answer 3

post condition :-

the loop terminates when ( r<y ) so one condition { r<y }

( q=q+1 ) q is increasing every time by 1 so q is simply counting loop count.

so r after execution

r = r - q y

(r=x) so

r = x - q y

x = r + q y

so option B

x = r + qy ^ r < y

Comments

@flash12

in the given code , each time the condition in while is satisfied , we increment q. we can say that for n iteration of while loop , q get incremented by n. So  we can also say that the while loop has iterated q times (since q is equal to n).

hence we can write

r=x-qy or x=r+qy

---

^ is a bitwise operator "xor" and how can 8 = 8 ^ True?

---

so,nice explanation 

 

post condition :-

the loop terminates when ( r<y ) so one condition { r<y }

( q=q+1 ) q is increasing every time by 1 so q is simply counting loop count.

so r after execution

r = r - q y

(r=x) so

r = x - q y

x = r + q y

so option B

x = r + qy ^ r < y

Answer 4

we can solve by taking some values and after check out with options.