CSCI-UA.0453-001 Theory of Computation

Fall 2013

---

General Information and Announcements

Solutions to HW 4,5 are available.

---

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: MW 3:30-4:45, CIWW 312

Professor: Subhash Khot, CIWW 416, 212-998-4859, Office hours: MW 2:30-3: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 “self-evident”.

Homework 1 Solutions: File1 File2

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 (3^nd Ed, 2^nd Ed will work too).

---