| L01 | Overview, Turing Machins | [Video] |
|---|---|---|
| L02 | Decidable and recognizable languages, the Church-Turing thesis, variants of TMs | [Video] |
| L03 | Existence of unrecognizable languages, universal TMs, towards reductions | [Video] |
| L04 | Mapping reducitons, some undecidable/unrecognizable languages | [Video] |
| L05 | Rice's theorem, Post's correspondence problem | [Video] |
| L06 | Time complexity, the class P, verifiers, the class NP | [Video] |
| L07 | The class NP, Non-deterministic TMs, P=NP? | [Video] |
| L08 | Polynomial time reductions, NP-completeness | [Video] |
| L09 | The Cook-Levin theorem, more NP-complete problems | [Video] |
| L10 | Cook/Karp/Levin reductions, decision vs. search, space complexity | [Video] |
| L11 | More space complexity, dealing with NP-hardness, approximation algorithms | [Video] |