| Concept | Notes | Video | Other |
|---|---|---|---|
| Introduction | NOTES | L01A-B | |
| Nondeterminism | NOTES | L02A-B | |
| Regular Expressions | notes | L03A | |
| The Pumping Lemma | NOTES | L03B | |
| Context-Free Grammars | notes | L04A-B | |
| Syntactic Structures | notes | L05A-B | |
| Push Down Automata | notes | L06A-B | |
| Equivalence of PDAs and CFGs | notes | L07A | |
| Turing Machines | notes | L08A | |
| The Church-Turing Thesis | notes, slides | L08B | |
| Turing Completeness | notes | L09A-B | |
| Countability | notes | L10A-B | |
| Foundations of Mathematics | notes | L11A-B | |
| Godel Incompleteness | notes | L12A-B | |
| Undecidability | notes | L13A | |
| Art of Reduction | notes | L13B | |
| Posts Correspondence Problem | notes | L14B | |
| Kolmogorov Complexity | notes | L14B | |
| Complexity Classes | notes | L15A-B | |
| In and around NP | notes | L16A-B | |
| In and around PSPACE | notes | L17A-B | |
| Relativization | notes | L18A-B | |
| Circuits | notes | L19A-B | |
| The Polynomial Hierarchy | notes | L20A | |
| Karp-Lipton Theorems | notes | L20B |
These notes are currently being expanded and rewritten into a book. Check back later!