CSCI 4602
Fall 2022
Notes

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

  9. Programs and computability
  10. Uncomputable problems
  11. Reductions between problems
  12. Using reductions to show that problems are not computable
  13. Partially computable sets and m-complete problems

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