15-453 - Formal Languages, Automata, and Computability

Spring 2015, Tuesday/Thursday 12:00-1:20 PM, Baker Hall 136A

Instructor:
Steven Rudich (rudich@cs), Gates 7219
Office Hours: Tuesday 1:30-2:30 PM

TAs:
Asa Frank (afrank@andrew)
Office Hours: Monday 5:30-7:00 PM

Nathan Dobson (ndobson@andrew)
Office Hours: Web 8:00 PM - 10:00 PM and Sun 8:00 PM - 9:30 PM

This course provides an introduction to formal languages, automata, computability, and complexity. The course consists of a traditional lecture component supported by weekly homework assignments and quizzes and a course project. There are two midterms and a final examination.

Topics

• Automata and Languages: finite automata, regular languages, pushdown automata, context-free languages, pumping lemmas.
• Computability Theory: Turing Machines, decidability, reducibility, the arithmetic hierarchy the recursion theorem, the Post correspondence problem.
• Complexity Theory: time complexity, classes P and NP, NP-completeness, space complexity, PSPACE, PSPACE-completeness, the polynomial hierarchy, randomized complexity, classes RP and BPP.

Textbook

Introduction to the Theory of Computation (3rd Ed.) by Michael Sipser, 2012.
Errata for 3rd Edition: http://math.mit.edu/~sipser/itoc-derrs3.1.html

Prerequisites

15-251 or 21-228.

Grading

Homework, 25%; Class participation, 5%; Quizzes, 5%; Midterm I, 15%; Midterm II, 15%; Final, 20%; Project, 15%. Attendance is required.

Quizzes

See Quiz Policy.

Homework

Homework is due one week after it is assigned and should be handed in at the beginning of class. Late homework will be accepted only under exceptional circumstances. All assignments must be typeset (exceptions allowed for diagrams). Each problem should be done on a separate page.

Each student is to do their own work and hand in their own homework individually. Collaboration is allowed, but references used (including books, articles, websites, people, including yourself) must be listed!

Project

See Project info.