In this lecture, Professor Demaine begins his analysis of decision problems from a parameterized perspective, as well as defining the general W hierarchy.

In this lecture, Professor Demaine finishes up NP-hardness, and the various techniques involved in such proofs.

In this lecture, Professor Demaine introduces Hamiltonicity.

In this lecture, Professor Demaine explains hardness proofs of games and puzzles, and graph theoretic problems, all reducing from 3-SAT.

In this lecture, Professor Demaine starts a series of lectures on satisfiability, including using SAT to prove NP-hardness.

In this lecture, Professor Demaine introduces the concept of 3-partition and its many variations, a starting point for NP-hardness reductions. Weak and strong NP-hardness proofs are seen in the context of other examples.

In this lecture, Professor Demaine gives a brief overview of the class, summarizing the prerequisite complexity theory and featuring two examples of hardness proofs in games.