**Class time**. 3:30-4:45pm, Monday/Wednesday, room 317 WWH.

First meeting: Wednesday, September 5.

Make up class.
Saturday Dec. 1, 2:00-3:15pm, room 202 WWH.

Second
make up class.
Sunday Dec. 16, 11:00-12:15pm, room 317 WWH.

**Exam Dates:** Midterm, Wed.
October 17. Final, December 19,
4:00-5:50pm, room 312 WWH (note changed room).

**Office hours**. Tuesday 4-5pm, Thursday 2-3pm, and by
appointment.

**Mailing list, home page**. There is a class mailing list,
csci_ua_0453_001_fa12. I send homework updates and other useful
information to this list. You should be automatically subscribed to the
list (I will send a test message in the first week of classes); if you
are not subscribed please join the list: see http://www.cs.nyu.edu/mailman/listinfo/csci_ua_0453_001_fa12

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

Broadly speaking, this course will be studying what can and cannot be computed, and when something can be computed how simply can it 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.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.
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**. There is no required text. I will be providing
handouts that cover the course material. There is no textbook that is
particularly close to my approach to the material. If you want a
textbook, you might consider: Michael Sipser, Introduction to the
Theory of Computation*,* Thomson. The second edition has the
advantage of including solutions to a selection of
problems. However, let me point out that the approach I 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.

Reading
guide. Basically, you should read the handouts I
will be preparing. These amount to the "textbook" for the course.

Here is a detailed lecture by lecture
reading guide.

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

Chapter 1: Mathematical background

Chapter 2: Finite Automata

Chapter 3: Pushdown Automata

Chapter 4: Decidability and Undecidability

Chapter 5: NP Completeness

Turing Machines

Homework 1

Homework 2

Homework 3

Homework 4

Homework 5

Homework 6

Homework 7

Homework 8

Homework 9

Homework 10

Homework 11

Homework 12

Sample midterm

Sample final

Last modified: December 10, 2012