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 necessarily required.
Professor: Subhash Khot, CIWW 416, 212-998-4859, Office hours, Graders: 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.
Textbook for the course: Introduction to the Theory of Computation, Michael Sipser (3nd Ed, 2nd Ed will work too).