Theoretical Computer Science II: Introduction to Computability and Complexity

Fall 2010

Instructor:

Kevin Matulef
matulef@gmail.com
FIT 4-608-3
(mobile) 15210897483
Office Hours: Mon 3-5pm

Teaching Assistants:

TA's will have office hours from 7:30-8:30pm the night before HW is due.

Chenggang Wu
wuchenggang0316@gmail.com

Guang Yang
regulus06@163.com

Course Information:

Time: Mon/Wed 1:30-3:05pm
Place: 6A115

TA session: Fri 7:20pm

Course Description , Syllabus

Homeworks:

Latex Template for HW

• HW 1, due 9/29
• HW 2, due 10/20
• HW 3, (extra credit), due 11/3
• HW 4, due 11/23
• HW 5, NEW Due Date: 12/9
• HW 6, due 12/24

References:

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