A. use the euclidean algorithm to compute the gcds of the following pairs of integers state how many iterations each one takes to compute, and the value of the potential s at each stage. verify that indeed si+1≤2/3si. i. (77,143) ii. (90, 504) ii. (376, 475) iv. (987, 1597)b. try to find pairs of inputs (x, y such that the number of iterations of euclid(x, y) is "large", that is, as close as possible to the upper bound of loga3/2(x+y) that we derived in lecture. can you come up with a hypothesis about what kinds of inputs yield the worst-case running time?

Explanation:

(a). given GCD (77,143)

143 = 77.1 + 66

77 = 66.1 + 11

66 = 11.6 + 0

∴ the gcd (77,143) = 11

the number of iterations = 3

(ii). GCD(90,504)

504 = 90.5 + 54

90 = 54.1 + 36

54 = 36.1 + 18

36 = 18.2 + 0

∴ the gcd(90,504) = 18

the number of iterations = 4

(iii). GCD(376,475)

475 = 376.1 + 99

376 = 99.3 + 79

99 = 79.1 + 20

79 = 20.3 + 19

20 = 19.1 + 1

19 = 1.19 + 0

∴ the gcd(376,475) = 1

the number of iterations = 6

(iv). GCD(987,1597)

1597 = 987.1 + 610

987 = 610.1 + 377

610 = 377.1 +233

377 = 233.1 +144

233 = 144.1 + 89

144 = 89.1 + 55

89 = 55.1 + 34

55 = 34.1 + 21

34 = 21.1 + 13

21 = 13.1 = 8

13 = 8.1 9+ 5

8 = 5.1 + 3

5 = 3.1 + 2

3 = 2.1 + 1

2 = 1.2 + 0

∴ the gcd(987,1597) = 1

the number of iterations = 15

(b). the pairs of inputs for which the number of iterations is large is given thus;

1. gcd(8,5)

8 = 5.1 + 3

5 = 3.1 + 2

3 = 2.1 + 1

2 = 1.2 + 0

the number of iterations from this is 4

2. also gcd(8,13)

13 = 8.1 + 5

8 = 5.1 + 3

5 = 3.1 + 2

3 = 2.1 + 1

2 =1.2 + 0

the number of iteration from this is 5

→ from the examples given, the worst case scenario occurs when the inputs are conservative Fibonacci numbers.

cheers, i hope this helps.