CS682 Spring 06
Theory of Computation
Course Information



Dexter Kozen
Upson 5143
255-9209 office
257-4579 home
592-2437 cell

Teaching Assistant

Zoya Svitkina
Upson 4106
255-8758 office


Kelly Patwell
Upson 5147
255-7790 office

Time and Place

MWF 2:30-3:20, Hollister 306

Office Hours

Dexter: by appointment.  Please contact Kelly.
Zoya: by appointment.  Please contact Zoya.

Course Administration


We have a course newsgroup, cornell.class.cs682.  All course announcements will be posted there; please check daily for new announcements.  You may also use the newsgroup for technical discussions, posting general questions about the homework, etc.  The course staff will try to respond to questions in a timely manner, or if you know the answer, feel free to post it yourself.  Please avoid giving away any hints on the homework though.


We are using the course management system, CMS.  Kelly has entered everyone who preregistered, but if you did not preregister, you are probably missing.  Please login to http://cms.csuglab.cornell.edu/ and check whether you exist.  There will be a list of courses you are registered for, and Com S 682 should be one of them.  If not, please send your full name and Cornell netid to Kelly so she can register you.  You can check your grades and submit homework in CMS.  There is a help page with instructions.



The main text for the course will be

This is essentially a collection of lecture notes and exercises from previous versions of this course. Unfortunately, the book will not hit the shelves until March 2006, so the publisher has kindly given us permission to distribute photocopies of an abridged version to students enrolled in the course.  These are available free of charge from Kelly.  However, to protect its copyright, the publisher has insisted on some restrictions.

  1. The photocopies are available only to students enrolled in the course.
  2. The photocopies must be returned at the end of the semester.
  3. The photocopies may not be photocopied.

I ask you to comply with these restrictions.  As an added incentive, Springer has generously supplied us with coupons for 20% off the list price.  You will receive a coupon when you return the photocopied version to Kelly.

Other excellent sources:

These titles are on reserve in the Engineering library, Carpenter Hall.


All handouts other than homework and exams will be available on the web in pdf or html format.  It is your responsibility to check often for new postings.  For viewing pdf files, we recommend Adobe Reader, available free of charge.

Homework and Exams

There will be biweekly homework sets consisting of 3-5 problems, due by 4pm on the due date.  You may collaborate on the homework in small groups.  If you collaborate, submit one copy of your solutions with the names of all collaborators.  Acknowledge all sources, including others in the class from whom you obtained ideas.  Please type or write legibly and staple.  There will be a significant point deduction for late homework without a good excuse.  Assignments and solutions will be posted in CMS.  Submit hardcopy in class or to Kelly by 4pm on the due date, or a .pdf, .ps, .doc, or .txt file in CMS.  Do not submit Latex source.

There will be two 72-hour takehome exams, open book and notes.  No collaboration is allowed on the exams.  Sign out the exam with Kelly Patwell in 5147 Upson.  Return the completed exam to Kelly within 72 hours after signing it out (she must be there to record the time, do not just slip it under the door), or submit it via CMS.  If you wish to submit your exam during non-business hours, you must submit it via CMS.

Graded homework and exams will be passed back in class, otherwise old homework and exams will be available from Kelly.

Approximate weights: Homework 50%, exams 25% each.  Note that the exams comprise a much more significant portion of your grade than the homework.  Exam questions are of roughly the same level of difficulty as the homework questions.

Due dates (subject to change):
HW1 F 2/3
HW2 W 2/15
HW3 M 2/27
HW4 F 3/10
Prelim: any 72-hour period from F 3/10 to 4pm F 3/17
Spring break M 3/20 - F 3/24
HW5 F 3/31
HW6 F 4/14
HW7 M 4/24
HW8 F 5/5
Final: any 72-hour period from F 5/5 to 4pm M 5/15

Regarding the homework:

Regarding proofs:

It is often difficult for beginning graduate students to get used to the style and level of detail we would like to see.  Many students, based on experience from their undergraduate days, tend to be overly formal.  Some are careless in their use of mathematical notation.  Some do not write in complete English sentences, but pepper their proofs with arrows and half-sentences and expect the reader to piece it together.

One of the goals of this course is to get you used to writing good proofs.  This is a good skill to cultivate, as you will soon be writing articles for publication.  Here are some rules of thumb to go by; please heed them well.

Soon after each homework assignment is due, solutions will be posted.  Please read them, because it will give you a good idea of the style and level of detail we expect.


Familiarity with the content of CS481 and (CS482 or CS681) is assumed.  In particular, we will assume knowledge of:

Approximate Syllabus

The course is organized around a few fundamental themes.  The exact coverage is subject to change.  Topics below will be covered as time permits; we will probably not have time to cover everything.