CS105 W10: Homework 02

Assigned: Friday January 15, 2010
Due: Friday January 22, 2010
  1. CLRS Problem 19-2
  2. CLRS Problem 20-1
  3. KT 5.1
  4. KT 5.3, but solve in O(n) time
  5. KT 5.6
  6. KT 5.7
  7. Show how to use the FFT to multiply two n-bit numbers in time O(n log n)
Extra Credit:
  1. KT 5.4
  2. KT 5.5