This site is subject to update through the term. This page was last modified Thursday January 15, 2026 at 11:33:30 EST.
Time: MW 11:00am - 12:15pm
Place: Swearingen 2A11 (Section 001) or remotely (Section J60)
The syllabus includes the course overview, homework and exam policies, graduate versus undergraduate requirements, quiz and final exam dates, final grade calculation information, academic integrity information, and a rough schedule of lecture topics.
Actual topics are only approximate.
| Spring 2024 | Spring 2025 | Spring 2026 | |
| Jan 08 | Jan 13 | Jan 12 | Overview, alphabets, strings,baby DFAs |
| Jan 10 | Jan 15 | Jan 14 | Formal def of DFA, computation, acceptance, regular languages, complement DFA |
| Jan 17 | Jan 22 | Jan 21 | Product DFA, def of A(w), reg langs closed under Boolean set ops, string matching, starting nondet |
| Jan 22 | Jan 27 | Jan 26 | Def of NFA, simulating an NFA, NFA->DFA by sets-of-states |
| Jan 24 | Jan 29 | Jan 28 | DFA minimization, intro to regexes |
| Jan 29 | Feb 03 | Feb 02 | Regular operations, regex->NFA, intro to GNFAs to show regex/NFA equivalence |
| Jan 31 | Feb 05 | Feb 04 | NFA -> regex (via state elimination), formal def of GNFAs |
| Feb 05 | Feb 10 | Feb 09 | State elimination example, some techniques for proving closure properties of regular languages |
| Feb 07 | Feb 12 | Feb 11 | DROP-ONE example (cont.); proving nonregularity: Myhill-Nerode theorem, Pumping Lemma |
| Feb 12 | Feb 17 | Feb 16 | Pumping Lemma examples, combined with closure properties; intro to Turing machines |
| Feb 14 | Feb 19 | Feb 18 | Formal def of Turing machines (TMs), instantaneous descriptions (IDs) |
| Feb 19 | (no lecture) | Feb 23 | Formal def of computation, language recognition, language decision; intro to Church-Turing thesis |
| Feb 21 | (no lecture) | Feb 25 | Church-Turing thesis: TMs capture intuitive notion of computation; TM modules for some basic operations |
| Feb 26 | Mar 03 | Mar 02 | Multitape TMs and their simulation with (1-tape) TMs; encoding finite math objects; a universal TM |
| Feb 28 | Mar 05 | Mar 04 | High-level algo descriptions, undecidability of ATM |
| Mar 11 | Mar 17 | Mar 16 | Enumerators and enumerability, basic theorems and proof techniques |
| Mar 13 | Mar 19 | Mar 18 | More basic (un)decidability results, computable functions, noncomputability, starting mapping reducibility |
| Mar 18 | Mar 24 | Mar 23 | m-reducibility: proof techniques, machines that output machines |
| Mar 20 | Mar 26 | Mar 25 | sample reductions from ATM and its complement, the editing problem |
| Mar 25 | Mar 31 | Mar 30 | proof that the editing problem is undecidable, intro to computational complexity, P and NP |
| Mar 27 | Apr 02 | Apr 01 | polynomial reductions, intro to NP-completeness, the SATISFIABILITY problem, P vs. NP |
| Apr 01 | Apr 07 | Apr 06 | Cnf formulas, CNF-SAT, the Cook-Levin theorem and its proof |
| Apr 03 | Apr 09 | Apr 08 | No NP-hard language is in P unless P=NP, restrictions of languages, CNF-SAT p-reduces to 3-SAT |
| Apr 08 | Apr 14 | Apr 13 | 3-SAT p-reduces to not-ALL_NFA (NP-hard) and to 3-colorability (NP-complete) |
| Apr 10 | Apr 16 | Apr 15 | 3-COL ≤p k-COL for every k ≥ 3, HP and HC reduce to each other |
| (no lecture) | Apr 21 | Apr 20 | complement of ALLNFA is NP-hard; starting space-bounded computation, PSPACE, guess tape to simulate nondeterminism |
| (no lecture) | Apr 23 | Apr 22 | Quantified Boolean formulas; TQBF is in PSPACE |
| Apr 22 | Apr 28 | Apr 27 | TQBF is NPSPACE-complete, thus PSPACE=NPSPACE; Savitch's Theorem; "Guess" primitive; ALLNFA is in PSPACE |
I will post announcements here from time to time.
Here is a link to Michael Sipser's Theory Of Computation course at MIT from Fall 2020 (course number 18.404J). We cover a proper subset of the topics there. (Thanks goes to Jacob Bagley for providing the link.)
The Java Formal Languages and Automata Package (JFLAP) is a free, easy-to-install, Java-based app for creating, manipulating, and simulating the computational models that you will learn about in this course, including (among others) automata and Turing machines.
Homework assignments will be posted on Blackboard.
This page last modified Thursday January 15, 2026 at 11:33:30 EST.