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).
- Solve the following recurrences:
- T(n) = 2T(n/2) + n3 for n >= 2;
T(1) = 1;
- T(n) = T(9n/10) + n for n >= 2; T(1) = 1;
- Solve the following recurrences:
- T(n) = 16T(n/4) + n2 for n >= 2; T(1) = 1; T(0) = 1;
- T(n) = 7T(n/3) + n2 for n >= 2; T(1) = 1; T(0) = 1;
- Solve the following recurrences:
- T(n) = T(sqrt(n)) + 1 for n >= 2; T(1) = 1;
- T(n) = 2 T(sqrt(n)) + 1 for n >= 2; T(1) = 1;
- Extra credit: Chapter 5, Page 246, Problem 1.