Homepage for CSCE 551
Theory of Computation
Spring 2024

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)

Syllabus

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, class by class

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

Announcements

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.

  1. Homework 1 due 1/29/2024
  2. Homework 2 due 2/12/2024
  3. Homework 3 due 2/26/2024
  4. Homework 4 due 3/18/2024
  5. Homework 5 due 4/1/2024
  6. Homework 6 due 4/10/2024
  7. Homework 7 due never

Supporting Materials

Past Exams

Course Notes

JFLAP

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

Homework assignments will be posted here.


This page last modified Monday April 22, 2024 at 13:47:26 EDT.