Home CPSC 326

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
  • Final Exam Topic List
  • Space Complexity
• Problem Sets
  • Problem Set 1
  • Problem Set 2
  • Problem Set 3
• In-class assignments:
  • DFAs
  • DFA Languages
  • NFAs
  • Regular Expressions
  • Non-Regular Languages
  • Context-Free Grammars
  • Turing Machines
  • More Turing Machines
  • Decidable Problems
  • Complexity Theory
  • Final Practice Problems

Copyright © 2024 Ian Finlayson | Licensed under a Creative Commons BY-NC-SA 4.0 License.