Theory of Computing

CSE 30151 | Spring 2022

Overview

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

Prerequisites

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.

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

Links

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

Schedule

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.

UnitDateTopicReadingDue
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

Staff

  • Brian DuSellInstructor
    Brian DuSell
    bdusell1@
  • Gang LiuGraduate TA
    Gang Liu
    gliu7@
  • Mahsa MitcheffGraduate TA
    Mahsa Mitcheff
    mmitchef@
  • Ken SibleGraduate TA
    Ken Sible
    ksible@
  • Jonathan AbbottUndergraduate TA
    Jonathan Abbott
    jabbott4@
  • Vito LinUndergraduate TA
    Vito Lin
    vlin2@
  • Sam ManfredaUndergraduate TA
    Sam Manfreda
    smanfred@
  • Colin McDonaldUndergraduate TA
    Colin McDonald
    cmcdona8@
  • Luke MillerUndergraduate TA
    Luke Miller
    lmille24@
  • Gabriel Silva SimõesUndergraduate TA
    Gabriel Silva Simões
    gsilvasi@

Office Hours

DayTimePersonLocation
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

Textbook

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

Acknowledgments

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.