This site is subject to update through the term. This page was last modified Thursday January 30, 2025 at 15:18:38 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.
| Spring 2024 | Spring 2025 | |
| Jan 08 | Jan 13 | Overview, alphabets, strings, baby DFAs |
| Jan 10 | Jan 15 | Formal def of DFA, computation, acceptance, regular languages, complement DFA |
| Jan 17 | Product DFA, def of A(w), reg langs closed under Boolean set ops, string matching, starting nondet | |
| Jan 22 | Def of NFA, simulating an NFA, NFA->DFA by sets-of-states | |
| Jan 24 | DFA minimization, intro to regexes | |
| Jan 29 | Regular operations, regex->NFA, intro to GNFAs to show regex/NFA equivalence | |
| Jan 31 | NFA -> regex (via state elimination), formal def of GNFAs | |
| Feb 05 | State elimination example, some techniques for proving closure properties of regular languages | |
| Feb 07 | DROP-ONE example (cont.); proving nonregularity: Myhill-Nerode theorem, Pumping Lemma | |
| Feb 12 | Pumping Lemma examples, combined with closure properties; intro to Turing machines | |
| Feb 14 | Formal def of Turing machines (TMs), instantaneous descriptions (IDs) | |
| Feb 19 | Formal def of computation, language recognition, language decision; intro to Church-Turing thesis | |
| Feb 21 | Church-Turing thesis: TMs capture intuitive notion of computation; TM modules for some basic operations | |
| Feb 26 | Multitape TMs and their simulation with (1-tape) TMs; encoding finite math objects; a universal TM | |
| Feb 28 | High-level algo descriptions, undecidability of ATM | |
| Mar 11 | Enumerators and enumerability, basic theorems and proof techniques | |
| Mar 13 | More basic (un)decidability results, computable functions, noncomputability, starting mapping reducibility | |
| Mar 18 | m-reducibility: proof techniques, machines that output machines | |
| Mar 20 | sample reductions from ATM and its complement, the editing problem | |
| Mar 25 | proof that the editing problem is undecidable, intro to computational complexity, P and NP | |
| Mar 27 | polynomial reductions, intro to NP-completeness, the SATISFIABILITY problem, P vs. NP | |
| Apr 01 | Cnf formulas, CNF-SAT, the Cook-Levin theorem and its proof | |
| Apr 03 | No NP-hard language is in P unless P=NP, restrictions of languages, CNF-SAT p-reduces to 3-SAT | |
| Apr 08 | 3-SAT p-reduces to not-ALL_NFA (NP-hard) and to 3-colorability (NP-complete) | |
| Apr 10 | 3-COL ≤p k-COL for every k ≥ 3, 3-SAT ≤p SUBSET-SUM ≤p PARTITION (both NP-complete); intro to PSPACE | |
| Apr 22 | TQBF is NPSPACE-complete and in PSPACE, thus PSPACE=NPSPACE, "Guess" primitive, EQREX is in PSPACE; Review |
I will post announcements here from time to time.
(1/30/2025) Here are links to all the homework handouts for this semester: Homework 1, Homework 2, Homework 3, Homework 4, Homework 5, Homework 6.
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 30, 2025 at 15:18:38 EST.