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 cant 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.)