Theory of Computing

CSE 30151 | Fall 2020

Overview

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.
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:

Staff


Instructor
David Chiang
dchiang@nd.edu

Graduate TA
Jongsuh Lee

Graduate TA
Yifan Yu

Undergraduate TA
Catherine FitzGibbons

Undergraduate TA
Katie McHugh

Undergraduate TA
Gabriel Simões

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

Schedule

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

Requirements

Component Points
Homework 8 × 30
Quizzes 2 × 60
Midterm exam 120
Final exam 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

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

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

Miscellaneous

Further Reading