CS 5114

Assignment 2

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) + n²

b. T(n) = 4T(n/2) + n²

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.