**Class time**. 3:30-4:45 Monday/Wed.

First meeting: tba.

**Exam Dates:** tba.

**Office hours**. tba.

**Mailing list, home page**. There will be a class
mailing list. I send homework updates and other useful
information to this list.

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

**Self-grading**. On the day the homeworks are due I will
be handing out solution sets. You are required to grade a copy
of your homework using the solution set as a guide and to hand
the graded copy in at the following class session. The
self-grading should indicate the mistakes in the original
solution and why they are mistakes. We will grade your original
solution and your self-grading. The purpose of this is to
enhance your understanding of the material.

To facilitate the management of the homework, I ask that you
do the following.

1. Write the solutions leaving space for your grading comments
and for our grading comments (e.g. margins on both sides, and
top and bottom, and don't use tightly spaced lines).

2. Hand in you solution in an envelope with your name on it. You
will need four envelopes in total: one for the homework, one for
the self-graded homework, and two for the following week's
homework. The intended schedule will be announced nearer the
time.

3. You may handwrite your homework, legibly of course, or
typeset it. The best way to typeset mathematical material is to
use Latex.

**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 I have
been writing and teaching this course from for several years.
Links to the chapters are below. I expect to be revising the
text this summer, and either the revised text will be available
for purchase at the start of the semester, or I will provide it
on an ongoing basis over the course of the semester. 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 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 my text. We will cover it in full.

Here
is a detailed lecture by lecture reading guide for the 2012
offering of 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).

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

Sample midterm (fall 2012)

Sample final (fall 2012)

Last modified: April 25, 2014