**Class time and location**. 11:00-1215, MW, room 512 WWH.

First meeting: Monday, January 25

**Exam Dates. **Midterm: Wednesday March 23, in class; Final:
Monday May 16, 10:00-11:50am.

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

**Mailing list, home page**. The class mailing list is csci_ua_0453_001_sp16@cs.nyu.

**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 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.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 on Monday at the start of class. Hand in
your self-graded solution on Wednesday, again, 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.

**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. 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 (this may get modified as the
course proceeds).

**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, last updated Jan 20, 2016

Chapter 2: Finite Automata, last updated, Jan 25, 2016

Chapter 3: Pushdown Automata, last updated Feb 29, 2016

Chapter 4: Turing Machines, last updated March 30, 2016

Chapter 5: Decidability and Undecidability last updated, April 5, 2016

Chapter 6: NP Completeness, last updated, May 02, 2016

Sample midterm

Sample final updated May 4, 2016

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 13 solution set problem 6

Last modified: May 02, 2016