V22.0453-001

Theory of Computation

Fall 2010


General Information and Announcements

 


Prerequisites

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

Endterm


 

Textbook

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