All notes in a single document
Module 1: Mathematical Preliminaries
| 1. Review of propositional logic | |
| 2. Review of first-order logic | |
| 3. Theorems and proofs | |
| 4. Mathematical foundations |
Module 2: Regular Languages and Finite-State Computation
| 5. Finite-state machines and regular languages | |
| 6. Regular expressions | |
| 7. Nonregular languages |
Module 3: Algorithms and computability
| 8. Programs and computability | |
| 9. Uncomputable problems | |
| 10. Reductions between problems | |
| 11. Using reductions to show that problems are not computable |
Module 4: Polynomial-Time Computability
| 12. Computational complexity and polynomial time | |
| 13. Nondeterminism and NP | |
| 14. NP-completeness | |
| 15. Examples of NP-complete problems | |
| 16. Beyond NP |
Practice questions for all of the sections
| Practice questions for all sections |