We’ll start today’s class by discussing complexity classes and NP-completeness. Then we’ll dive into a new worksheet on reductions (used differently than before).
Announcements for today:
- You have a tutorial quiz today. Assignment 5 (mainly on memoization/dynamic programming) will be released today at the usual time.
- We’ve posted some information about the final exam. See the Piazza post.
- Your second reading quiz on NP-completeness is due Thursday night.
Here are today’s clicker questions.