-
- Time
- TTh 12:45–1:35pm
- Location
- Zoom
- 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.
Office hours are listed below; all office hours are on Zoom.
| Tue | Wed | Thu | Fri | ||||
|---|---|---|---|---|---|---|---|
| 12:45–1:35pm | lecture | 12–2:30pm | Yu | 12:45–1:35pm | lecture | 11am–noon | McHugh |
| 1:45—3:00pm | Chiang | 2:30–3:30p | McHugh | 1:45—3:30pm | Chiang | 12–2pm | FitzGibbons |
| 7–9pm | Lee | 6–8pm | Lee | ||||
| 8–10pm | Simões | ||||||
Please read the notes (), including links to textbook readings and videos, before each class. 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.
We will discuss the material and work example problems during class. After class, you can access the recorded video ().
Unless otherwise indicated, each assignment is due on Friday at 5pm of the week in which it is listed.
| Unit | Date | Topic | Links | Due | |
|---|---|---|---|---|---|
| 08/11 | Welcome | ||||
| 08/13 | Proofs | ||||
| I | 08/18 | Finite automata | |||
| 08/20 | DFAs = NFAs | HW1 | |||
| 08/25 | Regular expressions to NFAs | ||||
| 08/27 | NFAs to regular expressions | HW2 | |||
| 09/01 | Non-regular languages | ||||
| 09/03 | Non-regular languages | Quiz 1 | |||
| II | 09/08 | CFGs and PDAs | |||
| 09/10 | CFGs = PDAs | HW3 | |||
| 09/15 | Non-context-free languages | ||||
| 09/17 | Non-context-free languages | HW4 | |||
| 09/22 | Review | Handout | |||
| 09/24 | Midterm | ||||
| III | 09/29 | Turing machines | |||
| 10/01 | Church-Turing thesis | ||||
| 10/06 | TM variants | ||||
| 10/08 | The universal TM | HW5 | |||
| 10/13 | Undecidability | ||||
| 10/15 | Undecidability | HW6 | |||
| 10/20 | Reducibility | ||||
| 10/22 | Computation histories | Quiz 2 | |||
| IV | 10/27 | P and NP | |||
| 10/29 | NP-completeness | HW7 | |||
| 11/03 | Cook-Levin theorem | ||||
| 11/05 | Polynomial reductions | HW8 due 11/10 | |||
| 11/10 | Polynomial reductions | ||||
| 11/12 | Review | Handout | |||
| Final |
| Component | Points |
|---|---|
| Homework | 8 × 30 |
| Quizzes | 2 × 60 |
| Midterm exam | 120 |
| Final exam | 120 |
| Total | 600 |
| Grade | Points |
|---|---|
| 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 |
Students are expected to attend all classes. Foreseeable unexcused absences should be discussed with the instructor ahead of time.
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 for a penalty. No problem can be submitted more than once. The late penalty is 10% per day, rounded down to the nearest point. That is, the credit you receive is ⌊0.9d×(max(0,s−1)+1)⌋, where s is the possibly fractional number of days late.
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.
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 |
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.
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.
 | The Universal Computer: The Road from Leibniz to Turing by Martin Davis. Short biographies of the pioneers of computability theory and their contributions. |
 | The Annotated Turing by Charles Petzold. Contains the text of Turing's 1936 paper with detailed and understandable commentary. |
 | Logicomix: An Epic Search for Truth by Christos Papadimitriou. Graphic novel about Bertrand Russell and the foundations of mathematics. |
 | The Golden Ticket by Lance Fortnow. Popular account of P and NP and the history and future of the question. |
Michael Sipser, Introduction to the Theory of Computation
