Office Hours: Mon 3-5pm
TA's will have office hours from 7:30-8:30pm the night before HW is due.
Time: Mon/Wed 1:30-3:05pmTA session: Fri 7:20pm
Course Description , Syllabus
Latex Template for HW
The texbook for the class is Michael Sipser's excellent Introduction to the Theory of Computation, second edition. More advanced material can be found in Christos Papadimitriou's Computational Complexity, and Sanjeev Arora & Boaz Barak's Computational Complexity: A Modern Approach (a draft of which can be found online). Additional references will be posted here.
Reference for HW 1: Nondetermism and the size of two-way finite automata, by Sipser and Sakoda.
Notes on the Recursion Theorem
Edmond's matching algorithm