There are four problems in this homework. They are from
- Exercise 12 of Lecture 1. (15 points)
- Exercise 23(a) of Lecture 1. (10 points)
- Exercise 26 of Lecture 1. (10 points)
- 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.