Homepage for CSCE 551
Theory of Computation
Spring 2025
This site is subject to update through the term. This page was
last modified Monday April 21, 2025 at 16:19:03 EDT.
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 2025, class by class
Spring 2024
Spring 2025
Jan 10
Jan 15
Formal def of DFA,
computation, acceptance, regular languages, complement DFA
Jan 17
Jan 22
Product DFA, def of
A(w), reg langs closed under Boolean set ops, string matching,
starting nondet
Jan 22
Jan 27
Def of NFA,
simulating an NFA, NFA->DFA by sets-of-states
Jan 29
Feb 03
Regular operations,
regex->NFA, intro to GNFAs to show regex/NFA equivalence
Jan 31
Feb 05
NFA -> regex (via
state elimination), formal def of GNFAs
Feb 05
Feb 10
State elimination
example, some techniques for proving closure properties of regular languages
Feb 07
Feb 12
DROP-ONE example
(cont.); proving nonregularity: Myhill-Nerode theorem, Pumping Lemma
Feb 12
Feb 17
Pumping Lemma
examples, combined with closure properties; intro to Turing machines
Feb 14
Feb 19
Formal def of
Turing machines (TMs), instantaneous descriptions (IDs)
Feb 19
(no class)
Formal def of
computation, language recognition, language decision; intro to
Church-Turing thesis
Feb 21
(no class)
Church-Turing
thesis: TMs capture intuitive notion of computation; TM modules for
some basic operations
Feb 26
Mar 03
Multitape TMs
and their simulation with (1-tape) TMs; encoding finite math objects; a
universal TM
Feb 28
Mar 05
High-level algo
descriptions, undecidability of A
TM
Mar 11
Mar 17
Enumerators and
enumerability, basic theorems and proof techniques
Mar 13
Mar 19
More basic
(un)decidability results, computable functions, noncomputability,
starting mapping reducibility
Mar 18
Mar 24
m-reducibility:
proof techniques, machines that output machines
Mar 20
Mar 26
sample reductions
from A
TM and its complement, the editing problem
Mar 25
Mar 31
proof that the
editing problem is undecidable, intro to computational complexity, P
and NP
Mar 27
Apr 02
polynomial
reductions, intro to NP-completeness, the SATISFIABILITY problem, P
vs. NP
Apr 01
Apr 07
Cnf formulas,
CNF-SAT, the Cook-Levin theorem and its proof
Apr 03
Apr 09
No NP-hard language
is in P unless P=NP, restrictions of languages, CNF-SAT p-reduces to 3-SAT
Apr 08
Apr 14
3-SAT p-reduces to
not-ALL_NFA (NP-hard) and to 3-colorability (NP-complete)
Apr 10
Apr 16
3-COL ≤
p k-COL for
every
k ≥ 3, HP and HC reduce to each other
Apr 22
Apr 21
TQBF is
NPSPACE-complete and in PSPACE, thus PSPACE=NPSPACE, "Guess"
primitive, EQ
REX is in PSPACE; Review
Announcements
I will post announcements here from time to time.
(4/14/2025) Here are the extra exercises for grad students and honors
students: hw-grad-sp25.pdf. It is due
April 25. Submit to Blackboard.
(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.
Supporting Materials
Past Exams
Course Notes
-
Here are my current (occasionally updated)
COURSE NOTES.
-
Here are some old course notes of mine for
this course. These are a bit out of date, but still may be useful. I
intend to update them during the course, so expect these notes to change.
-
Here is a proof that
SUBSEQ(L) is regular for any language L. There is a simpler proof
using well-quasi-order theory.
-
Here are my notes on Minimum DFAs.
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 on Blackboard.
This page last modified Monday April 21, 2025 at 16:19:03 EDT.