Week 13: NP Completeness 2

Week of 4/12

Mandatory videos

For Tuesday

NP-Completeness Proof for Independent Set (17:59)

More NP-Completeness Proofs (17:58)

For Thursday

The Cook-Levin Theorem for Proving SAT is the Hardest Problem in NP (14:17 - across 6 short videos)

Optional bonus videos

NP-Completeness Proof for Hamiltonian Cycle (and Traveling Salesman) (15:29)

In class:

Example Problems

Out:

Hoomework #7, Lecture review assignment #13