Steven Rudich (rudich@cs), Gates 7219
Office Hours: Tuesday 1:30-2:30 PM
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.
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
15-251 or 21-228.
Homework, 25%; Class participation, 5%; Quizzes, 5%; Midterm I, 15%; Midterm II, 15%; Final, 20%; Project, 15%. Attendance is required.
See Quiz Policy.
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!
See Project info.