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 |