V22.0453001
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 selfcontained. Experience with programming,
basic algorithms and data structures would be useful, but not required.
Professor: Subhash Khot – WWH 416 , 2129984859, Office hours : Tues 10:4511:45.
Course Syllabus (Click on the link)
Homeworks and Exams
There will be 5 homeworks (50%), a takehome
midterm (20%), and a takehome endterm (30%).
Textbook
Textbook
for the course:
Introduction to the Theory of Computation, Michael Sipser (2^{nd} Ed.).