Textbook: J. Watrous, Introduction to the Theory of Computing: Lecture notes for CS 360, version of June 27, 2017. (A Creative Commons license applies; see the cover page.)

This term’s offering was basically following Watrous’ text, accompanied by some complementary notes and videos. The assignments are heavily weighted, 63%. To explore more on theoretical computer science, consider taking cs 365 and cs 462.

These notes cover the foundations of computability theory. Topics include set theory and countability, alphabets and languages, deterministic and nondeterministic finite automata (DFAs/NFAs), regular expressions and languages, context-free grammars and pushdown automata, Turing machines, decidability, and computational complexity.