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. Nonregular languages | |
7. Regular expressions | |
8. Equivalence of Regular Expressions and Finite-State Machines |
Module 3: Algorithms and computability
Module 4: Polynomial-Time Computability
14. Computational complexity and polynomial time | |
15. Nondeterminism and NP | |
16. NP-completeness | |
17. Examples of NP-complete problems | |
18. Beyond NP |