Theory of Computation, CSCI-UA.0453.001

Instructor. Guy Kindler, gkindler@cs.nyu.edu.

Class time and location. Mondays and Wednesdays 3:30-4:45PM, at CIWW 201.
First meeting: Monday, January 2

Exam Dates. Midterm: Wednesday, March 21, in class; Final: TBA.

Office hours. Monday 5-6pm, and by appointment.

Mailing list, home page TBA.

Course Goal and Syllabus. The goal of this class is to develop your ability to evaluate and write mathematical claims in computer science, so as to be able to:

  •  Judge when a problem is solved (and equally important, when it is not yet solved).
  •  Explain such mathematical claims clearly and precisely.
  • Broadly speaking, this course will be studying what can and cannot be computed, and when something can be computed how simply it can be done. The specific topics covered will include proofs techniques, finite automata and regular languages, pushdown automata and context free languages, decidable and undecidable problems, and NP-completeness.

    Attendance. You are strongly encouraged to attend all the classes of the course. The course material would be quite challending for one to study on their own relying just on the notes. The interaction and group energy allowed by class attendance is extremely helpful for most people.

    Assignments. There will be more or less weekly homeworks. Late homeworks will not be accepted (except in the event of illness or other unavoidable circumstances). If for some reason you will be unable to hand in a homework on time, please discuss it with me beforehand.   While you may discuss homework problems with your fellow students, you must write up your solutions in your own words.  Be aware that you are unlikely to perform well on exams unless you gain practice at problem solving on the homeworks.

    To facilitate the management of the homework, I ask that you do the following.
    1. Write the solutions leaving space for grading comments (e.g. margins on both sides, and top and bottom, and don't use tightly spaced lines).
    2. Hand in you solution on Monday at the start of class.
    3. You may handwrite your homework, legibly of course, or typeset it. The best way to typeset mathematical material is to use Latex.

    Further Comments. If you are unable to completely solve a problem (or you cannot solve it at all) please write down your thoughts on how the problem should be approached, and where you approach breaks down. Or if you have given an answer that you know is incorrect, please indicate what the error is.

    Academic Integrity.  Please take note of  the course and departmental policy on this matter:  http://www.cs.nyu.edu/web/Academic/Undergrad/academic_integrity.html

    Assessment. Homeworks will comprise 40% of the overall grade, the midterm 20% and the final 40%.  However, if the grade on the final is better than the midterm grade it will replace the midterm grade.  Exams will be closed book.

    Required text. The required text is the book Richard Cole has been writing and teaching this course from for several years.  If you want a published textbook, you might consider: Michael Sipser, Introduction to the Theory of Computation, Thomson.  The most recent edition has the advantage of including solutions to a selection of problems. However, let me point out that the approach we will be taking diverges quite a bit from this text. Another possible text is: Daniel I.A. Cohen, Introduction to Computer Theory.  This text provides a lot of examples and can be quite helpful. However, it does not cover material for the whole course, and the approach it takes differs even more from the one I will be using in this course.

    Homework Details. You may handwrite your homework, legibly of course, if you prefer, rather than typeset it.  In my experience, when typesetting, often too much effort is spent on the appearance of the homework and minor yet significant errors are overlooked.  Also, if your homework solution has multiple pages, please staple them; please don't fold down the corners or use paperclips, for the pages are much more likely to come apart. Finally, if handwriting, please use an easy to read ink color (blue or black, not red or green).

    Past Courses
    This course will be quite similar to the one I gave last year. This course is very strongly based on the course with the same name given by Richard Cole the year before. You can look at the homepage of that course here (but note that I deviate from Richard's course in some places). I wil try to mention the points where our course deviates from Richards notes.