Theory of Computing

CSE 30151 | Spring 2020

Overview

Time
TTh 2–3:15pm
Location
127 Hayes-Healy
Instructor
David Chiang
Prerequisites
Discrete Mathematics (CSE 20110) or equivalent. You especially need to be comfortable with sets, tuples, functions, relations, and graphs; and writing proofs by contradiction and by induction.
Required text
Michael Sipser, Introduction to the Theory of Computation
3rd International Edition
ISBN: 1-133-18781-1
Price: about $15 (Amazon)
Errata
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
Links
The following sites will be used in this course:
  • Sakai for submitting assignments and receiving grades
  • Piazza for questions and answers
  • Notes and assignments will be linked from here, but you can also clone the Github repository

Staff


Instructor
David Chiang
dchiang@nd.edu
OH: MW 3–5
179 Fitzpatrick

Graduate TA
Darcey Riley
OH: T 3:30–4:30, F 2–3 in 150B Fitzpatrick; F 3–4 in 150M Fitzpatrick

Undergraduate TA
Hannah Burchfield
OH: Th 6–8pm
Innovation Lounge

Undergraduate TA
Sophie Johnson
OH: Th 8–10pm
Innovation Lounge

Undergraduate TA
Chris Ray
OH: T 7–9pm
Innovation Lounge

Undergraduate TA
Chan Hee Song
OH: W 7–9pm
Innovation Lounge

Schedule

Notes are posted as Jupyter notebooks. If you want to fiddle with the examples, install Tock, clone the Git repository, and run jupyter notebook in your working copy.

Links that are grayed out point to notes and assignments from Spring 2018.

Unless otherwise indicated, each assignment is due on Friday at 5pm of the week in which it is listed.

Unit Week of Topic Assignment Due
01/14 Introduction and background
I 01/21 Finite automata HW1
01/28 Regular expressions HW2
02/04 Non-regular languages CP1
02/11 Review and midterm
II 02/18 Context free grammars, pushdown automata HW3
02/25 CFG = PDA HW4
03/03 Non-context-free languages CP2
Spring break
III 03/17 Turing machines HW5
03/24 The universal TM and undecidability HW6
03/31 Reducibility CP3
04/07
Holy Week
Review and midterm
IV 04/14 P and NP HW7
04/21 NP-completeness CP4
04/28 Review HW8
05/07 10:30amFinal exam

Requirements

Component Points
Homework (HW) 8 × 30
Course project (CP) 4 × 30
Midterm exams (ME) 2 × 60
Final exam (FE) 120
Total 600
GradePoints
A
A−
560–600
540–559
B+
B
B−
520–539
500–519
480–499
C+
C
C−
460–479
440–459
420–439
D 360–419
F 0–359

Project

Throughout the semester, you will implement some of the ideas you've learned in a series of text-processing tools.

  • You can work in teams of up to three. Each team member should contribute a roughly equal amount of work.
  • You can write in C++ (including all standard libraries except <regex>) or Python (including all standard libraries except re). Python is recommended. You can also write in another language with permission from the instructor.

In Project 1, you'll implement nondeterministic finite automata (NFA). Nondeterminism (essentially, unbounded parallelism) is one of the core concepts in the course, and implementing it will demonstrate how to simulate nondeterminism on deterministic hardware.

In Project 2, you'll write a parser for regular expressions and combine it with NFAs to build a regular expression matcher like grep. Your implementation will be asymptotically much faster than an implementation that uses Perl or Python's built-in regular expressions.

In Project 3, you'll use your regular expression engine to implement a fragment of sed. You'll also show how, in principle, any computer program could be compiled into this fragment of sed.

In Project 4, you'll extend your regular expression matcher to handle backreferences. You'll show how this extended matcher can be used to (slowly) solve the Boolean satisfiability problem and therefore any problem in NP.

Policies

Attendance

Students are expected to attend all classes. Foreseeable unexcused absences should be discussed with the instructor ahead of time.

Late Work

For excused absences (including job interviews), coursework submissions will be accepted late by the same number of days as the excused absence.

Otherwise, you may submit some problems on time for full credit, and other problems late with a penalty of 10% per day (rounded down to the nearest point). No problem can be submitted more than once.

Copyright

All course materials written by the instructor and published on this website are licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License, which prohibits reuse for commercial purposes.

All course materials written by the instructor and distributed privately (including through Sakai) should not be redistributed in any way; doing so is a violation of both US copyright law and the University of Notre Dame Honor Code.

Honor Code

Students in this course are expected to abide by the Academic Code of Honor Pledge: “As a member of the Notre Dame community, I will not participate in or tolerate academic dishonesty.”

The following table summarizes how you may work with other students and use print/online sources:

Resources Solutions
Consulting allowed not allowed
Copying cite not allowed
See the CSE Guide to the Honor Code for definitions of the above terms.

If an instructor sees behavior that is, in his judgement, academically dishonest, he is required to file either an Honor Code Violation Report or a formal report to the College of Engineering Honesty Committee.

Students with Disabilities

Any student who has a documented disability and is registered with Disability Services should speak with the professor as soon as possible regarding accommodations. Students who are not registered should contact the Office of Disability Services.

Miscellanous

Further Reading