CSE 421 Assignment #5
Autumn 2005

Due: Wednesday, November 2, 2005, 1:30 pm.

Reading Assignment: Kleinberg and Tardos Chapter 6.1 - 6.4.

Problems: (see Grading Guidelines sheet before answering) Do problems 1 and 2, and two problems from 3, 4, or 5. Problem 6 is extra credit.

1. The Blum-Floyd-Pratt-Rivest-Tarjan satisfies the following recurrence: T(n) < cn for n < 50, and T(n) < T(n/5) + T(3n/4) + cn for n >= 50. Show that T(n) <= dn for some d.

2. Give upper bounds for T(n) in each of the following examples. You may assume T(n) is constant for n <= 2.
   1. T(n) = 16T(n/4) + n²
   2. T(n) = 7T(n/3) + n²
   3. T(n) = T(n-1) + n
   4. T(n) = T(sqrt(n)) + 1

3. Kleinberg and Tardos, Chapter 5, Problem 1, Page 246.

4. Kleinberg and Tardos, Chapter 5, Problem 3, Page 246-247.

5. Kleinberg and Tardos, Chapter 5, Problem 6, page 248

6. Extra credit: Kleinberg and Tardos, Chapter 5, Problem 7, page 248-249. I found this one to be tricky - the approach I took was to find a way with 2n probes to identify an n/2 x n/2 grid that is guaranteed to have a local minimum.