Homepage for CSCE 551
Theory of Computation
Spring 2024

This site is subject to update through the term. This page was last modified Monday March 25, 2024 at 13:47:45 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

Announcements

I will post announcements here from time to time.

(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 March 25, 2024 at 13:47:45 EDT.