CSCI-UA.0453-001

Theory of Computation

Spring 2023


General Information and Announcements

 Note: Final exam is on May 10, 10-11:50, in the usual classroom (Silver 208). Note that the day is a Wednesday!


Prerequisites

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.

 


Administrative Information

Lectures: TTh 9:30-10:45, Silver 208

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

 

Homework 2 Solutions

 

Homework 3 Solutions

 

Homework 4 Solutions

 

Homework 5 Solutions

 


 

Textbook

Textbook for the course: Introduction to the Theory of Computation, Michael Sipser (3nd Ed, 2nd Ed will work too).

Notes:

Basics

FA-1 FA-2 FA-3 FA-4

CFL-1 CFL-2 CFL-3

D-1 D-2 D-3 D-4 D-5

NP-1

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.

NPC NPC-1 NPC-2 NPC-3