CSE 421 Assignment #5
Winter 2009

Due: Wednesday, February 11, 2009, 1:30 pm.

Reading Assignment: Kleinberg and Tardos 5.1-5.5

Problems: (see Grading Guidelines sheet before answering)
Note: In the following, you can generally ignore rounding issues (just round down to an integer).

  1. Solve the following recurrences:

    1. T(n) = 2T(n/2) + n3 for n >= 2; T(1) = 1;

    2. T(n) = T(9n/10) + n for n >= 2; T(1) = 1;

  2. Solve the following recurrences:

    1. T(n) = 16T(n/4) + n2 for n >= 2; T(1) = 1; T(0) = 1;

    2. T(n) = 7T(n/3) + n2 for n >= 2; T(1) = 1; T(0) = 1;

  3. Solve the following recurrences:

    1. T(n) = T(sqrt(n)) + 1 for n >= 2; T(1) = 1;

    2. T(n) = 2 T(sqrt(n)) + 1 for n >= 2; T(1) = 1;

  4. Extra credit: Chapter 5, Page 246, Problem 1.