This is not a homework, but just a collection of problems from Lectures 30 of Jeff Erickson's notes. The problems are on concepts surrounding P, NP, and NP-completeness. For the last two 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 23 of Lecture 30.
  4. Exericse 24 of Lecture 30.

Take a look at these problems. We will solve some of them on the last day of classes.