## Description

1. Using the Master Theorem discussed in class, solve the following recurrence

relations asymptotically. Assume T(1) = 1 in all cases. (25 Pts.)

(a) T(n) = T(9n/10) + n

(b) T(n) = 16T(n/4) + n

2

(c) T(n) = 7T(n/3) + n

2

.

(d) T(n) = 7T(n/2) + n

2

.

(e) T(n) = 2T(n/4) + √

n log2 n.

2. Sometimes, you might be interested in solving a recurrence relation exactly

(i.e., not just asymptotically). Note that when you are interested in solving

a recurrence relation exactly, you cannot use the Master Theorem. You can

often do so by using the method of repeated substitutions (and observing the

pattern and algebraically simplifying). You should have learnt this technique in

discrete math courses. You can refresh your memory by solving the following

two problems.

• T(1)=3 and for all n ≥ 2. T(n) = T(n − 1) + 2n − 3. (10 Pts.)

• T(1)=1 and for all n ≥ 2, a power of 2, T(n) = 2T(n/2) + 6n − 1. (15

Pts.)

3. You are given an array A of n distinct integers (indexed 1 through n) which are

not arranged in any particular order. You want to determine the smallest and

the largest integer in the array. Observe that the problem is trivial if n = 2.

For the sake of simplicity, you can assume that n is a power of two. (25 Pts.)

1 CSCI 3650

(a) Develop an algorithm based on the divide and conquer principle to do so.

Present your idea in simple English. (5 Pts.)

(b) Now express the same idea in the form of a pseudocode. Specifically,

write a recursive function Min-Max(A,i,j) that returns the smallest and

the largest integer (the output will be a struct type as it consists of two

elements) in the portion of the array starting from index i to j using the

divide and conquer principle. Note that We can solve the original problem,

by simply calling your function with parameters of A, 1, n. (7 Pts.)

(c) Develop a recurrence relation for the running time of your algorithm. State

both the recurrence relation and the base condition for it. Assume that

the comparison of two integers from the array is the only time consuming

operation. Time spent doing anything else can be ignored. (5 Pts.)

(d) Solve the recurrence relation exactly (i.e., not just asymptotically) and

determine the running time (i.e., number of comparisons) needed to solve

a problem instance of size n. (8 Pts.)

4. Given an array A[1..n] of natural numbers, find values of i and j with 1 ≤ i ≤

j ≤ n such that

X

j

k=i

A[k]

is maximized.

(a) Present a brute force algorithm for this problem which runs in time O(n

3

).

(5 Pts.)

(b) With little bit of thinking, it is not too difficult to come up with an algorithm that runs in time O(n

2

). Present such an algorithm. [Hint: Use an

auxiliary array to maintain partial sums] (8 Pts.)

(c) Devise an algorithm based on divide and conquer technique for solving

this problem so that your algorithm runs in time O(n log n). (12 Pts.)

2 CSCI 3650