CSCIUA.0453001
Theory of Computation

Fall 2013

Solutions
to HW 4,5 are
available.
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 necessarily
required.
Professor: Subhash Khot, CIWW 416, 2129984859, Office hours: MW 2:303:30.
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 “selfevident”.
Homework 1 Solutions:
File1 File2
Textbook
Textbook
for the course: Introduction to the Theory of Computation, Michael Sipser (3^{nd} Ed, 2^{nd} Ed will work
too).