Theory of Computing

CSE 30151 | Spring 2022


Course Description

Introduction to formal languages and automata, computability theory, and complexity theory with the goal of developing understanding of the power and limits of different computational models. Topics covered include:

  • regular languages and finite automata
  • context-free grammars and pushdown automata
  • Turing machines; undecidable languages
  • the classes P and NP; NP completeness


Discrete Math (CSE 20110) and Data Structures (CSE 20312/24312). You especially need to be comfortable with sets, tuples, functions, relations, and graphs; and writing proofs by contradiction and by induction.

Tue/Thu 2-3:15pm
DeBartolo Hall 138
Brian DuSell


  • Canvas will be used for submitting assignments, receiving grades, and online Q&A
  • Syllabus


Please do the assigned readings from the textbook before each class. Unless otherwise stated, each assignment is due at 11:59pm on Thursday of the week in which it is listed.

Jan 11Welcome
Jan 13Strings, languages, and proofs0 (p. 1-25)Survey
IJan 18Finite automata1.1 (p. 31-47)
Jan 20DFAs = NFAs1.2 (p. 47-63)HW1
Jan 25Regular expressions1.3 (p. 63-69)
Jan 27REs = NFAs1.3 (p. 69-76) · DFA Min.HW2 · PA Team
Feb 1Non-regular languages1.4 (p. 77-82)
Feb 3Non-regular languagesPA1
Feb 8ReviewStudy Guide
Feb 10Midterm Exam 1
IIFeb 15CFGs2.1 (p. 101-111)
Feb 17PDAs2.2 (p. 111-116)HW3
Feb 22CFGs = PDAs2.2 (p. 117-125)
Feb 24More on CFLs2.4 (p. 130-131)HW4
Mar 1Non-CFLs2.3 (p. 125-129)
Mar 3Non-CFLsPL for CFLs
Spring Break
IIIMar 15Turing machines3.1 (p. 165-175)
Mar 17TM variants3.2 (p. 176-187)PA2 · HW5
Mar 22ReviewStudy Guide
Mar 24Midterm Exam 2
Mar 29Recognizers, Deciders, and NTMs4.1 (p. 193-201)
Mar 31Universal TM4.2 (p. 201-210)HW6
Apr 5Undecidability5.1 (p. 215-220)
Apr 7Reducibility5.1-5.3 (p. 220-238)PA3
IVApr 12Mapping reducibility, PCP, and time complexity7.1-7.2 (p. 275-291)
Apr 14P and NP7.3 (p. 292-298)HW7
Apr 19NP-completeness7.4 (p. 299-311) · NP-completeness
Apr 21Polynomial reductions7.5 (p. 311-322)
Apr 26Optional review session
7-8:30 PM in DeBartolo Hall 138
Study GuideHW8 · All late assignments
Reading Days
May 4Final Exam
10:30 AM-12:30 PM in DeBartolo Hall 138


  • Brian DuSellInstructor
    Brian DuSell
  • Gang LiuGraduate TA
    Gang Liu
  • Mahsa MitcheffGraduate TA
    Mahsa Mitcheff
  • Ken SibleGraduate TA
    Ken Sible
  • Jonathan AbbottUndergraduate TA
    Jonathan Abbott
  • Vito LinUndergraduate TA
    Vito Lin
  • Sam ManfredaUndergraduate TA
    Sam Manfreda
  • Colin McDonaldUndergraduate TA
    Colin McDonald
  • Luke MillerUndergraduate TA
    Luke Miller
  • Gabriel Silva SimõesUndergraduate TA
    Gabriel Silva Simões

Office Hours

Mon4-5DuSellFitzpatrick 150A
5-7MitcheffFitzpatrick 150B
7-8MillerFitzpatrick 150
Tue3:30-5:30ManfredaDeBartolo B011
5:30-6:30LiuFitzpatrick 150B
7:30-9:30McDonaldDeBartolo B011
Wed3-5LinFitzpatrick 150
5-7DuSellFitzpatrick 150A
7-8MillerFitzpatrick 150
8-10SimõesDeBartolo B011
Thu4-6AbbottDeBartolo B011
6-8SibleFitzpatrick 150B


The following textbook is required for this course:

Michael Sipser, Introduction to the Theory of Computation, 3rd Edition

The 3rd edition of this book has both a domestic hardcover version and an international softcover version. Although the numbering of problems differs between the two, their contents are otherwise the same. You may use either one for this course, but please ensure that in either case, you get the 3rd edition and not an earlier edition.

Domestic Hardcover
Domestic Hardcover
International Softcover
International Softcover


The design and materials for this course were strongly influenced by past instructors, including: Dr. David Chiang, Dr. Marina Blanton, Dr. Peter Kogge, and Dr. Satyaki Sikdar.