CPSC 326: Theoretical Foundations of Computing
- Syllabus
- Course Notes:
- Course Introduction
- Deterministic Finite Automata
- More Deterministic Finite Automata
- Non-deterministic Finite Automata
- DFA-NFA Equivalence
- Regular Expressions
- More Regular Expressions
- Non-Regular Languages
- Context-Free Grammars
- Push-Down Automata
- Non Context-Free Languages
- Turing Machines
- Turing Machine Variants
- The Church-Turing Thesis
- Reducibility & Undecidable Problems
- The Recursion Theorem
- Complexity Theory
- Complexity & P
- The Class NP
- NP-Completeness
- More NP-Complete Problems
- Space Complexity
- Final Exam Topic List
- Problem Sets
- In-class assignments: