The problem numbers refer to the textbook on Jeff Erickson's algorithms page. Note that all the problems I have assigned only require us to come up with recursive algorithms. It is fine for the running time to be exponential.
  1. Exercise 2 (a,b,c) of Chapter 2 (Backtracking). (20 points)
  2. Exercise 3 (a) of Chapter 2. (10 points)
  3. Exercise 5 (b) of Chapter 2. (10 points).

The homework is due in class on Tuesday, February 19. Please pay attention to the policy on collaboration outlined in the syllabus.