Theory of Computation, V22.0453.01

Instructor. Richard Cole, WWW430, tel: 998-3119,

Class time. 11:00-12:15pm, Tuesday/Thursday, room 102, Warren Weaver Hall.
First meeting: Thursday, September 6.

Final exam date.  Tuesday, December 18,  10:00-11:50am.

Office hours. Tuesday/Thursday, 2:15-3:15pm and by appointment.

Mailing list, home page. There is a class mailing list at; please join this list; it is intended for discussion of course related materials and announcements if there are any (to subscribe, follow the instructions on the mailing list web page).   The course home page can be accessed from the department home page ( by following the links to course home pages and then to this course, or directly at

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:

  •  Judge when a problem is solved (and equally important, when it is not yet solved).
  •  Explain clearly and precisely why an algorithm is correct and what it computes.
  • The specific topics covered will include proofs techniques, finite automata and regular languages, pushdown automata and context free languages, Turing Machines and decidable and undecidable problems.

    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.

    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 final grade.  Exams will be closed book.

    Required text.  Michael Sipser, Introduction to the Theory of Computation, PWS.
  (Richard Cole)
    Last modified: Aug 29 2001