- Term
- Spring 2018
- Time
- TTh 2–3:15pm
- Location
- 136 DeBartolo
- 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.

- 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
- Slack for informal discussion
- Notes and assignments will be linked from here, but you can also clone the Github repository
- Tutorial on using LaTeX and TikZ

Graduate TA

Satyaki Sikdar

ssikdar@nd.edu

Wed 4–6pm

B011 DeBartolo

Undergraduate TA

Connor Higgins

chiggin7@nd.edu

Wed 8–10pm

B011 DeBartolo

Undergraduate TA

Laura Syers

lsyers@nd.edu

Tues 8–10pm

212 Cushing

Component | Points |
---|---|

Homework (HW) | 8 × 30 |

Course project (CP) | 4 × 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 |

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.

[SP17] links point to notes from last year's offering in Spring 2017.

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

Unit | Week of | Topic | Assignment Due | |
---|---|---|---|---|

01/16 | Introduction and background [slides] | |||

I | 01/23 | Finite automata | HW1 | |

01/30 | Regular expressions | HW2 | ||

02/06 | Non-regular languages | CP1 | ||

02/13 | Review and midterm | |||

II | 02/20 | Context free grammars, pushdown automata | HW3 | |

02/27 | CFG = PDA [SP17] | HW4 | ||

03/06 | Non-context-free languages [SP17] | CP2 | ||

Spring break | ||||

III | 03/20 | Turing machines [SP17] | ||

03/27 Holy Week |
The universal TM and undecidability [SP17] | |||

04/03 | Reducibility [SP17] | CP3 | ||

04/10 | Review and midterm | |||

IV | 04/17 | P and NP [SP17] | ||

04/24 | NP-completeness [SP17] | CP4 | ||

05/01 | Review | |||

05/08 10:30 | Final exam |

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

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 would be 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. Although this has a large speed penalty, you'll show how this extended matcher can be used to solve the Boolean satisfiability problem.

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

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

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 10% per day (rounded down to the nearest point). No problem can be submitted more than once.

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.

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 |

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.

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.

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. Only tangentially related to this course, but did I mention it's a graphic novel? | |

The Golden Ticket by Lance Fortnow. Popular account of P and NP and the history and future of the question. |