Algorithms  Assignment 1: Loop Invariants

EECS 340/454: Algorithms 
Assignment 1: Loop Invariants

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