Theory of Computation

Spring 2022

General Information and Announcements

Endterm is on Mon, May 16, 2022 8:00AM-9:50AM in SILVER 208


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: TTh 9:30-10:45, Kimmel 914

Professor: Subhash Khot, WWH 416, 212-998-4859, Office hours: Wed, 10:30-12:30.

Grader: TBA.

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).


Tentative homeworks are as below. There could be changes as we go along. Deadlines will be announced; typically, deadlines will be 7-10 days after all relevant topics have been covered in class.



Homework 1 Solutions-1 Solutions-2


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).



FA-1 FA-2 FA-3 FA-4


D-1 D-2 D-3 D-4 D-5


I started writing notes on P/NP, but realized that I already have notes from an earlier course. These are below. There is some repetition in the background material and the intended audience was slightly different, but should hopefully be reasonable.