Overview
-
- Time
- TTh 2–3:15pm
- Location
- 126 DeBartolo Hall
- Instructor
- Dr. 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's Introduction to the Theory of Computation, in either the 2nd or 3rd edition:
2nd Edition, 2005
ISBN: 0-534-95097-3
Links: Amazon errata
3rd Edition, 2012
ISBN: 1-133-18779-X
Links: Amazon errata
On reserve in the Engineering Library.
3rd International Edition, 2012
ISBN: 1-133-18781-1
Links: 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 this site, but you can also:
- clone the Github repository
- view live Jupyter notebooks in Binder (experimental)
Staff
Graduate TA
Justin DeBenedetto
jdebened@nd.edu
MW 5–6pm, 213 Cushing
Undergraduate TA
Frank Cipollone
fcipollo@nd.edu
M 6–7pm, 213 Cushing
Undergraduate TA
Jennifer Long
jlong8@nd.edu
M 10–11pm, 213 Cushing
Requirements
| Component | Points |
|---|---|
| Homework (HW) | 9 × 30 |
| Course projects (CP) | 3 × 30 |
| Midterm exams (ME) | 2 × 60 |
| Final exam (FE) | 120 |
| Total | 600 |
| Letter 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 |
Schedule
| Unit | Dates | Topic | Assignment Due | |
|---|---|---|---|---|
| 01/12, 01/14 | Introduction and background | |||
| I | 01/19, 01/21 | Finite automata | HW1 | |
| 01/26, 01/28 | DFA = NFA = regular expressions | HW2 | ||
| 02/02, 02/04 | Non-regular languages | HW3 | ||
| 02/09, 02/11 | Review and midterm | Study guide Closure proofs |
||
| II | 02/16, 02/18 | Context free grammars, pushdown automata | HW4 | |
| 02/23, 02/25 | CFG to PDA and PDA to CFG | CP1 | ||
| 03/01, 03/03 | Non-context-free languages | HW5 | ||
| Spring break | ||||
| III | 03/15, 03/17 JPW |
Turing machines | HW6 | |
| 03/22, 03/24 Easter |
The universal TM and undecidability | CP2 | ||
| 03/29, 03/31 | Reducibility | HW7 | ||
| 04/05, 04/07 | Review and midterm | Study guide | ||
| IV | 04/12, 04/14 | P and NP | HW8 | |
| 04/19, 04/21 | NP-completeness | CP3 | ||
| 04/26 | More NP-completeness | HW9 | ||
| 05/06 10:30–12:30 | Final exam | Study guide | ||
Policies
Attendance
Students are expected to attend all classes. Foreseeable absences should be discussed with the instructor ahead of time.
Late Work
In the case of a serious illness or other excused absence, as defined by university policies, 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 20% per day (rounded down to the nearest point). No problem can be submitted more than once.
Honor Code
All work that you submit must be your own; that is, it must represent your own understanding, in your own words. Discussion of problems is encouraged, but writing solutions together or looking at other students' solutions is not allowed. Any print or online resources that you use must be cited properly; use of solution manuals is not allowed.
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.