Theory of Computation, V22.0453.01

Instructor. Richard Cole, 417 WWH, tel: 998-3119,

Class time. 2:00-3:15pm, Monday/Wednesday, room 317 WWH.
First meeting:  Wednesday, September 7.
No class: Monday, October 10 (university holiday)

Final Date: Monday, December 19, 2:00-3:50pm, 317 WWH.

Office hours. Tuesday 4:30-5:30pm, Wednesday 11:00am-12:00pm, and by appointment.

Mailing list, home page. There is a class mailing list; please join it.  See:

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:

  •  Judge when a problem is solved (and equally important, when it is not yet solved).
  •  Explain such mathematical claims clearly and precisely.
  • 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.

    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:

    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. Nearer the time, I will prepare a guide relating the handouts to the lectures.

    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

    To get a sense of the handouts you can follow the links from the fall 2009 course page. I plan to  rewrite them a bit this summer, but the approach is not going to change much.  Rather, I will add problems and maybe rework a few of the proofs and explanations.

    Course Content
    Chapter 1: Mathematical background
    Chapter 2: Finite Automata
    Chapter 3: Pushdown Automata and Context Free Languages
      (There is still 1 section to be added)
    Chapter 4: Decidability and Undecidability
    Turing Machines
    Chapter 5: NP-Completeness 

    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 14 

    Last modified:December 5, 2011