Problem 1
The greatest common divisor (GCD) of two integers a and b is defined as the largest integer that can divide both a and b without a remainder. For example, the GCD of 30 and 54 is 6, whereas the GCD of 7 and 5 is 1. The following procedure was developed by Euclid to compute the greatest common divisor of two positive integers a and b. In this exercise, we will prove the correctness of this algorithm.
procedure Euclidean(a, b)
1 x ← a
2 y ← b
3 while x 6= y do
4 if x y then
5 x ← x−y
6 else
7 y ← y −x
8 return x
(a) State the loop invariant for the while loop in this procedure.
(b) Prove the loop invariant.
(c) Prove that procedure Euclidean always terminates provided that a and b are positive integers.
(d) Using the termination property of your loop invariant, prove that procedure Euclidean computes and returns the greatest common divisor of a and b.
Problem 2
Let A and B be two arrays, each consisting of n numbers sorted in increasing order. We are also given a number x and would like to find and return i and j such that A[i] + B[j] = x. If no such pair exists, we would like to return FALSE. We would like to develop an algorithm to solve this problem in linear time.
(a) Using pseudo-code, describe an algorithm that correctly solves this problem in linear time.
(b) Explain graphically how your algorithm works.
(c) Using loop invariants, prove that your algorithm is correct.
(d) Show that the worst-case runtime of your algorithm is Θ(n).
Problem 3
Two species are sharing planet Kepler-442b: Pisidians and Lydians. Members of either species roam individually. They can run into each other only in pairs (randomly) and whenever any two individuals run into each other, they fight. Since Pisidians are stronger and Lydians have magical powers, the outcome of a fight is always the same:
• If two Lydians fight, one of the Lydians dies and the other survives.
• If two Pisidians fight, both Pisidians die and a new Lydian comes to existence.
• If a Pisidian and a Lydian fight, the Lydian dies and the Pisidian survives.
At the beginning of time, there were m Lydians and n Pisidians on Kepler-442b. Observing that there will be only one individual left on Kepler-442b at eternity, identify the species of the eternal individual as a function of m and/or n. (Hint: Describe the process using a loop and define a loop invariant.)
