The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
442 views

Consider the following program operating on four variables $u, v, x, y$, and two constants $X$ and $Y$.

x, y, u, v:= X, Y, Y, X;    
While (x ≠ y)  
do
    if (x > y) then x, v := x - y, v + u;
    else if (y > x) then y, u:= y - x, u + v;  
od;
print ((x + y) / 2);  print ((u + v) / 2);  

Given $X > 0 \land Y > 0$, pick the true statement out of the following:

  1. The program prints $\text{gcd}(X, Y)$ and the first prime larger than both $X$ and $Y$.
  2. The program prints $\text{gcd}(X, Y)$ followed by $\text{lcm}(X, Y)$.
  3. The program prints $\text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$.
  4. The program prints $\frac1 2 \times \text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$.
  5. The program does none of the above.
in Algorithms by Boss (29.5k points)
edited by | 442 views
+1
if we take X=5 ; Y =7

then A follows ; please check
0
Hi Guys,

First of all thanks to all of you for providing awesome solution.  One method is solving by small example. is there any other way to solve this problem ?

2 Answers

+8 votes
It prints with $gcd(x,y)$ and $lcm(x,y)$.

Consider $x,y,u,v=17,3,3,17$.

$X=14$, $v=20$

$X=11$, $v=23$

$X=8$, $v=26$

$X=5$, $v=29$

$X=2$, $v=32$

$Y=1$, $u=35$

$X=1$, $v=67$

This is the value obtained.

Lastly, printing $(x+y)/2$ and $(v+u)/2$ gives $1$ and $51$.
by (281 points)
edited by
0
what about option c..????
+3 votes

Greatest Common Divisor of two number can be calculated using Euclid's Algorithm[1]

$$\begin{align}gcd(X,0) &= X \\ gcd(X,Y) &= gcd(Y,X \%Y)\end{align}$$

For $X,Y > 0$ this algorithm can be simplified as follows

$$gcd(X,Y) = \left\{\begin{matrix} X & X=Y& \\gcd(X-Y,Y)&X>Y & \\ gcd(X,Y-X)&X<Y & \end{matrix}\right.$$

Out of observation we learn that the given program is performing the same operation on two variable $x$ and $y$ initialized to $X$ and $Y$ respectively. Loop terminated with $x=y$, therefore $(x+y)/2$ i.e., average of two will return $x$ (or $y$), which is essentially $gcd(X,Y)$.

Next, let us propose a loop invariant[2] for this program[3]

$$2 X Y = (x \times v) + (y \times u)$$

The correctness of this program depends on this invariant, which must be true prior to the first iteration of the loop, during the execution of loop and with the termination of the loop it must express some useful property that program exhibits. Let's briefly show these three things.

  1. Initialization: The fact that this loop invariant holds prior to the first iteration of the loop can be seen by plugging in initial values of $x,y,u$ and $v$.
  2. Maintenance: Let us assume this loop invariant holds before $i^{th}$ iteration and we need to show that it holds after $i^{th}$ iteration as well. During $i^{th}$ iteration for $x>y$, $x = (x-y)$ and $u = (u+v)$. Substitue these new values in loop invariant we get $$\begin{align}2XY & = (x-y) \times v + y(u+v) \\ & = (x \times v) + (y \times u)\end{align}$$ And same will also be true for $x<y$.
  3. Termination: Loop terminates with $x=y$ and as shown earlier that $x=y=gcd(X,Y)$. Therefore, $$\begin{align}2XY & = (x \times v) + (x \times u) = x(u+v) \\ 2XY & = gcd(X,Y)(u+v) \end{align} $$ 

Rearranging above equation gives us[4]

$$\frac{XY}{gcd(X,Y)} = LCM(X,Y) = \frac{u+v}{2}$$

HTH


REFERENCES

  1. GCD using Euclid's Algorithm
  2. Introduction to Algorithms, CLRS, 3rd edition, 2.1, Pg.18
  3. Edsger Dijkstra lecture at University of Newcastle 1992
  4. Reduction by the greatest common divisor

P.S In competitive examinations like GATE/TIFR the better strategy for such unfamiliar program is to try executing the program on different values, observe the result and compare with given options. However, in my opinion, understanding the underlining crux of such problems (when we are outside examination hall) is more important than just getting answers.

by Active (4.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,807 questions
54,711 answers
189,259 comments
79,687 users