CSC 321 Spring 2002

Assignment 3

Due: Monday, April 29^th

Write up solutions to each of the following problems:

1. Problem 3-1(a) and (b) (pp. 57-58 in CLRS).
   
2. Problem 3-3(a) (p. 58 in CLRS).
   
3. Solve the following recurrence relations. This means finding a closed form and then expressing that in Q-notation.
   • T(n) = T(n-1) + 2; T(1) = 2
   • T(n) = T(n-1) + n²; T(1) = 1
   • T(n) = 2T(n/2) + n²; T(1) = 1
     
4. Problem 4-2 (p. 85 in CLRS).