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