Theory of Computation

Fall 2010

General Information and Announcements



Basic knowledge of  discrete mathematical structures (sets, graphs, functions, etc) and proof techniques (induction, proof by contradiction etc)  is assumed.  A brief overview of basics will be given in the first lecture.

Other than this, the course should be self-contained. Experience with programming, basic algorithms and data structures would be useful, but not required.


Administrative Information

Lectures: T Th  9:30-10:45,  WWH 317

Professor: Subhash Khot – WWH 416 , 212-998-4859,   Office hours : Tues  10:45-11:45.

Course Syllabus   (Click on the link) 

Homeworks and Exams

There will be 5 homeworks (50%), a take-home midterm (20%), and a take-home endterm (30%). 



Homework 1   Solutions

Homework 2   Solutions

Midterm          Solutions

Homework 3   Solutions

Homework 4  Solutions

Homework 5  Solutions




Textbook for the course:    Introduction to the Theory of Computation,  Michael Sipser  (2nd Ed.).