Week 15: NP Completeness 2

Week of 12/3

Mandatory videos

Monday

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

More NP-Completeness Proofs (17:58)

Wednesday

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:

Lecture review

Due:

Lecture review, Homework #7