CSCI 570 Homework 5
Due September 30th
1 Graded Problems
1. Give the asymptotic running time of the following recurrences if they can be solved with the Master Theorem. Otherwise, indicate that the Master Theorem
does not apply.
a. T(n) = 3T(n/3) +
b. T(n) = 2T(n/2)+nlogn. c. T (n) = 7T (n/3) + n2 + 2n. d. T(n) = 2nT(n/2) + nn.
e. T (n) = 7T (n/2) + n2 + 1.
2. Suppose you are given an ascending sorted array that is circularly rotated right. For example, [1,2,3,4,5] becomes [4,5,1,2,3] when rotated by 2 posi- tions. Give an algorithm that finds the smallest element in O(log n) time.
3. Solve Kleinberg and Tardos, Chapter 5, Exercise 2. 4. Solve Kleinberg and Tardos, Chapter 5, Exercise 3.
2 Practice Problems
1. Reading Assignment: Kleinberg and Tardos, Chapter 5.
¡Ì
n.
1