Week 12: NP Completeness 1

Week of 4/5

Mandatory videos

P, NP, and NP-Completeness; Identifying NP-Complete Problems

For Tuesday

Watch before class:

P, NP, and NP-Completeness

Watch during class:

Proving NP Completeness

For Thursday

Proving that Integer Programming is NP-Complete

In class:

Example Problems, review homework #5

Out:

Lecture review assignment #13