Due: February 14, 2001
1. Write recursive and iterative procedures for finding the greatest common
divisor of two integers m and n . Choosing a value of n =
run both these programs and determine the average case time complexity
of the algorithms (in terms of the number of procedure calls or loops).
Compare the result with the theoretical value given in class and computed
within the program.
2. Solve the recurrence relation:
T(n) = 2T(n - 1) + n ; for n > 2 with T(1) = 1
Prove that your result is true using mathematical induction.
3. a. Use a divide and conquer strategy to design an algorithm which
will find the maximum (MAX) and the next-highest (NEXT)
elements in an array of distinct integers. If T(n) is the number
of comparisons between array elements required by the algorithm
determine the recurrence relationship that is satisfied by T(n).
Hence find T(n) as an exact function of n.
b. If the third highest element is also required, how are the
algorithm, the recurrence relation, and its solution modified?
[algorithms should be written in pseudo high-level code]
4. For each of the following recurrence relations, assume that T(1) = 1 and
that n is a power of 2. Find the order of the function T(n) from the divide
and conquer theorem. Hence, or otherwise, determine an exact form for T(n).
a. T(n) = 3T(n/2) + n2
b. T(n) = 4T(n/2) + n2
5. Code up and run the divide and conquer solution and the O(n) solution
for the maximum longest subsequence problem which we discussed in
class. Demonstrate that both your solutions work on the n = 10 problem and
on an n = 20 problem of your own choosing.