1 10 points Consider the following algorithm procedure alg1a

1. (10 points) Consider the following algorithm:

procedure alg1(a, b : positive integers)

x := a

y := b

while y not equal 0

r := x mod y

x := y

y := r

return x

(a) What does alg1 return with input a = 50, b = 75? Note: for full credit, Include enough work to trace the execution of the algorithm on these inputs. Clearly label the output of the algorithm in your answer.)

(b) Is this algorithm finite? That is, is its computation guaranteed to terminate no matter which positive integers are chosen for a and b? Note: for full credit, give your answer (yes or no) and justify it. If your answer is yes, the justification should explain why the algorithm can’t possibly go into an infinite loop no matter what inputs are chosen (think carefully about the type of the inputs and the loop condition). If your answer is no, you need to find an example where the algorithm never returns output because it goes into an infinite loop.)

Solution

Hi,

The algorithm given down has no proper indentation. I have assumed the indentation as per the question

procedure alg1(a, b : positive integers)

x := a

y := b

while y not equal 0 {

r := x mod y

x := y

y := r

}

{if there is no boundary for a loop it will only excute the first statement until the loop exists then y will be no longer zero and the total program will be infinate loop. So i have given braces for the following statements.}

return x

then after the loop termination x will be returned and coming to the answers of the question:

A)

the starting set of x,y values would be 50,75 and r is 50 and the order follows like below

(50,75) : r=50 iteration 1

(75,50) :r=25 iteration 2

(50,25) :r=0 iteration 3

and x,y becomes (25,0) where while loop breaks and value of x i.e. 25 will be returned.

B) yes the loop is finite because at least at one point the r value becomes 1 because we are dealing with the remainders so if we encounter 1 then the r would be 0 and loop will break