**Final exam date**. Thursday December
21, 10:00-11:50am, room 513 WWH

**Class time**. 9:30-10:45pm, Tuesday/Thursday, room 513, Warren Weaver
Hall.

First meeting: Tuesday, September 5.

**Midterm Date: **Tuesday, October 24, in class.

**Office hours**. Tuesday/Thursday 11-12, and by appointment.

**Mailing list, home page**. There is a class mailing list; please
join it (see http://www.cs.nyu.edu/mailman/listinfo/v22_0453_001_fa06);
it is intended for discussion of course related materials and announcements
if there are any (to subscribe, follow the instructions on the mailing list
web page). The course home page can be accessed from the department
home page (http://www.cs.nyu.edu/) by following the links to course home
pages and then to this course, or directly at http://www.cs.nyu.edu/courses/fall06/V22.0453-001/index.html

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

The specific topics covered will include proofs techniques, finite automata and regular languages, pushdown automata and context free languages, Turing Machines and decidable and undecidable problems, and NP-completeness.Judge when a problem is solved (and equally important, when it is not yet solved). Explain clearly and precisely why an algorithm is correct and what it computes.

**Assignments**. There will be more or less weekly homeworks comprising
problems drawn from the textbook and elsewhere. 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.

**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**. The 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**. Michael Sipser, Introduction to the Theory
of Computation*,* Thomson. The second edition has some modest advantages
in that in includes solutions to a selection of problems; however, it
is OK to use the first edition.

**Another text**. Daniel I.A. Cohen, Introduction to Computer
Thoery. 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 in places from the one being used in this course.

**Homework Details**. I encourage you to handwrite your homework,
legibly of course, 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).

Homeworks and handouts.

Homework
1

Homework 2

Homework
3

Homework 4

Homework 5

Homework 6

Homework 7

Homework 8

Homework 9

Homework 10

Homework
11

Homework 12

Homework 13

Homework 14

Sample Midterm

Sample Final

Turing
Machines handout

Finite
Automata handout

Finite Automata, Part 2 handout

Finite Automata, Part3 handout

Last modified: December 13, 2006