CSCIUA.0453001
Theory of Computation

Spring 2023

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, WWH 416, 2129984859, Office hours: Wed 10:0012:00.
Grader: Kamalesh Neerasa, kn2359 AT N Y U
Tutor: Vaibhav Mavi, vm2241 AT N Y U
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).
Tentative
homeworks are as below. There could be changes as we
go along. Deadlines will be announced; typically, deadlines will be 710 days
after all relevant topics have been covered in class.
Homework 1 Solutions1 Solutions2
Textbook
Textbook
for the course: Introduction to the Theory of Computation, Michael Sipser (3^{nd} Ed, 2^{nd} Ed will work
too).
Notes:
I started writing notes on P/NP, but realized that I already have notes from an earlier course. These are below. There is some repetition in the background material and the intended audience was slightly different, but should hopefully be reasonable.