This site is subject to update through the term. This page was last modified Monday April 22, 2024 at 13:47:26 EDT.
Time: MW 11:00am - 12:15pm
Place: Swearingen 2A11 (Section 001) or remotely via APOGEE (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.
| Jan 08 | Overview, alphabets, strings, baby DFAs |
| Jan 10 | 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.
(3/29/2024) This is about the graduate exercises. Here are my notes on self-reference in computation. If you are taking the course for graduate or Honors College credit, then read Section 6.1 of the Sipser text, read Sections 1 and 2 of these notes, and do Exercises 2.2, 2.4, 2.5, 2.6, 2.12, and (especially) 2.16 from those notes. (The other exercises are optional; Exercise 2.1 is well worth the effort!) These exercises are due on Friday April 12, 2024 before 11:30pm. Submit your answers to the CSE Dropbox portal. You are free to discuss and work together on the questions and answers with anyone or anything (including other students in the class, me, or ChatGPT), but you must at least write down the answers yourself and say who/what you worked with or derived answers from.
NOTA BENE: Although I am allowing use of AI, I don't recommend leaning heavily on it. The questions in the handout require precise and to-the-point answers. AI provides answers that may look smart to a layperson but include lots of irrelevant detail and are usually completely inadequate for the precise answers needed. (Students who copied answers from ChatGPT in the past generally got zero credit. There was no Honor Code violation, because they properly cited their source.)
(1/6/2024) Here are all the homework handouts for this semester. Homeworks 1-6 are each meant to prepare for the corresponding quizzes (1-6). All due dates are Mondays except the last, which is on Wednesday. Answers and hints to selected exercises will be posted on CSE Dropbox after the homeworks are due. Homework 7 is not to be handed in; it is to prepare for the final exam.
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 here.
This page last modified Monday April 22, 2024 at 13:47:26 EDT.