Theory of Computation
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.
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%).
Textbook for the course: Introduction to the Theory of Computation, Michael Sipser (2nd Ed.).