CSCI-UA.0453-001
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 self-contained. Experience with programming,
basic algorithms and data structures would be useful, but not necessarily
required.
Professor: Subhash Khot, WWH 416, 212-998-4859, Office hours: Wed 10:00-12: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 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.
Homework 1 Solutions-1 Solutions-2
Textbook
Textbook
for the course: Introduction to the Theory of Computation, Michael Sipser (3nd Ed, 2nd 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.