CSE-830

Code and course material for MSU's "CSE 830: Design and Theory of Algorithms"

CSE 830: Design & Theory of Algorithms

Documents for CSE 830 - Week 15

NP-Completeness Theory

Starting: 12/7

Videos for Tuesday, Dec 8th

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

More NP-Completeness Proofs (17:58)

Videos for Thursday, Dec 10th

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)