The problems in this homework are from Lectures 30 of Jeff Erickson's notes. Each of the five exercises is worth 10 points. For the last three problems, prove that they are NP-complete, and not just that they are NP-hard.
  1. Exercise 3 of Lecture 30.
  2. Exercise 13 of Lecture 30.
  3. Exercise 14 of Lecture 30.
  4. Exercise 23 of Lecture 30.
  5. Exericse 24 of Lecture 30.

The homework is due in class on Thursday, May 4.