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

First meeting: Tuesday, September
4.

**Final Date: **Thursday December 20, 10:00-11:50, room 813 WWH. Note unusual
location.

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

**Mailing list, home page**. There is a class mailing list: http://www.cs.nyu.edu/mailman/listinfo/v22_0453_001_fa07;
please join it. 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/fall07/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, decidable and undecidable problems, and NP-completeness.Judge when a problem is solved (and equally important, when it is not yet solved). Explain such mathematical claims clearly and precisely.

**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.

Reading guide. Here is
a list of the readings to accompany each
lecture.

**Another text**. 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 in places from the one being
used in this course.

A Useful Tool. JFLAP is a
free application which allows one to construct and visualize finite
automata and languages of various sorts. I recommend downloading it.
See http://www.cs.duke.edu/csed/jflap/.

**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).

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

Finite Automata handout

Finite Automata, Part 2 handout

Finite Automata, Part 3 handout

CNF handout

Computability handout

CFG computability

Reductions: string problems

Undecidability continued

NP Completeness

NP Completeness II

Turing Machines handout

GNFA handout

Last modified: December 04, 2007