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.