Time

TTh 2–3:15pm

Location

126 DeBartolo

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.

Data Structures (CSE 20311) is recommended but not required for group programming assignments. If you haven't taken this course or equivalent, you may want to join a group with students who have.

Required text

Michael Sipser, Introduction to the Theory of Computation
3rd International Edition
ISBN: 9781133187813, 9788131525296
Price: about $25
Why this is legal
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:

• Notes and assignments will be linked from here, but you can also clone the GitHub repository
• Ed for questions and answers
• Canvas for submitting and grading assignments

Notes are posted as Colab notebooks. You should be able to use them in your browser, but if you want to use them on your own machine, install Tock, clone the Git repository, and run jupyter notebook in your working copy.

Items that are grayed out are from Spring 2024 and will be updated.

Week of	Topic	Assignment
01/13	Welcome Languages Proofs Glossary of math terms (for reference) Making machines with Tock (optional) LaTeX/TikZ tutorial (optional)
01/20	Deterministic finite automata NFAs = DFAs Neural networks (optional)	HW1 (due 01/24)
01/27	Regular expressions to NFAs NFAs to regular expressions	HW2 (due 01/31)
02/03	Non-regular languages More non-regular languages	CP1 (due 02/07)
02/10	Context-free grammars Pushdown automata CFGs to PDAs Deterministic PDAs (optional)	HW3 (due Thurs 02/13)
02/17	PDAs to CFGs Non-context-free languages	HW4 (due 02/21)
02/24	Non-context-free languages Turing machines	CP2 (due 02/28)
03/03	Turing machine variants	Midterm exam (03/04)
	Spring break (no class)
03/17	Nondeterministic TMs RAM machines The universal TM	HW5 (due 03/21)
03/24	Undecidability Are you smarter than a computer? (optional) Reducibility	HW6 (due 03/28)
03/31	Rice’s Theorem Computation histories	CP3 (due 04/04)
04/07	P and NP NP-completeness	HW7 (due 04/11)
04/14 Holy Week	Cook-Levin theorem Polynomial reducibility	CP4 (due Tues 04/22)
04/21	Polynomial reducibility	HW8 (due Tues 04/29)
04/28	Conclusion (no class Thurs 05/01)
05/05		Final exam

Component	Points
Homework	8 × 30
Programming projects	4 × 30
Midterm exam	120
Final exam	240
Participation	30
Total	750

Grade	Points
A A−	700–750 675–699
B+ B B−	650–674 625–649 600–624
C+ C C−	575–599 550–574 525–549
D	450–524
F	0–449

In Project 1, you'll implement nondeterministic finite automata (NFAs). 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.

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

For excused absences (e.g., documented illness, travel for athletics, job interview), 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 for a penalty. No problem can be submitted more than once. The late penalty increases by 10% per day and stops increasing when it reaches 50%; thereafter, it remains at 50% until the final exam date, after which no work may be submitted.

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 Canvas) 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.

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 printed/online sources:

	Resources	Solutions
Consulting	allowed	cite
Copying	cite	not allowed

See the CSE Guide to the Honor Code for definitions of the above terms.

If the 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.

Any student who has a documented disability and is registered for accessibility support should speak with the professor as soon as possible regarding accommodations. Students who are not registered should contact Sara Bea Accessibility Services.