The problem numbers refer to the textbook on Jeff Erickson's algorithms page.
  1. Exercise 3 of Chapter 1 (Recursion). Once you come up with a candidate algorithm, write a recurrence that describes the number of moves it makes. That is a sufficient answer, you don't need to solve the recurrence. Exactly how many moves does your algorithm make when the number of disks n equals 4? (15 points)
  2. Exercise 4 (a) of Chapter 1. Again, it suffices to write the recurrence for the number of moves without solving it. (10 points)
  3. Exercise 9 (a,b,c) of Chapter 1. (15 points)
  4. Exercise 11 (b,c) of Chapter 1 (10 points). You don't have to solve 11 (a) but I encourage you to think about the claim we are being asked to prove there.

If you wish to learn more about the methods needed to solve the recurrences in these problems, you can consult the notes Appendix II: Solving Recurrences on Jeff Erickson's page.

The homework is due in class on Tuesday, February 4. Please pay attention to the policy on collaboration outlined in the syllabus. In particular, you will get the most out of home work if either you work on your own or collaborate with a fellow student or two in a reasonable way. We will evaluate the originality of your writing while reviewing your work.