There are four problems in this homework. They are from Jeff Erickson's notes.
  1. Exercise 12 of Lecture 1. (15 points)
  2. Exercise 23(a) of Lecture 1. (10 points)
  3. Exercise 26 of Lecture 1. (10 points)
  4. Exercise 1 of Lecture 3. (15 points) Recall that in writting a recursive definition for LIS, we ended up having to write a write a recursive definition for a constrainted version: the LIS with elements larger than x. It is possible that something similar is needed in some parts of this problem. Also, please note that we are only asking for a recursive definition, not an algorithm (using memoization or dynamic programming, we'll cover those in the subsequent homework).

The homework is due in class on Tuesday, February 21.