Week 15: NP Completeness 2 Week of 12/7 Mandatory videos NP-Completeness Proof for Independent Set (17:59) More NP-Completeness Proofs (17:58) Optional bonus videos NP-Completeness Proof for Hamiltonian Cycle (and Traveling Salesman) (15:29) The Cook-Levin Theorem for Proving SAT is the Hardest Problem in NP (14:17 - across 6 short videos) In class: HW 6 Review; Example Problems Out: Lecture review assignment #15 Previous Next