Theory of Computation

Fall 2013

General Information and Announcements

Solutions to HW 4,5  are available. 



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 necessarily required.


Administrative Information

Lectures: MW 3:30-4:45, CIWW 312

Professor: Subhash Khot, CIWW 416, 212-998-4859, Office hours: MW 2:30-3:30.

Course Syllabus (Click on the link)

Homeworks and Exams

There will be 5 homeworks (30%), midterm (30%) and endterm (40%).


Note:  in the homeworks, you must show all the steps (e.g. while converting NFA to regular expression) and give justification/proof unless the answer or conclusion is “self-evident”.



Homework 1  Solutions: File1   File2


Homework 2  Solutions


Homework 3  Solutions 


Homework 4  Solutions


Homework 5  Solutions




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