Introduction to the Theory of Computation, Third Edition
Michael Sipser
Course Technology, Inc.

  • Exams: Three exams, each worth 20% of the final grade. The first two exams focus on material in the immediately preceding segment of the course. The third exam covers primarily later material, but may also cover material from earlier in the course.
  • Written Assignments: Eight problem sets, comprising 40% of the grade. Some problems sets may be replaced by one or more in-class exercises.
  • Reading: You are responsible for completing all assigned readings before the class indicated in the schedule on the wiki, whether or not the material is covered in lectures.
  • Cooperation policy: Permitted, but if you do cooperate the solutions must be written up individually (not copied).
  • Use of outside materials: The use of course bibles or any online materials is not permitted and will be reported to the Academic Panel if detected.
  • Assignments and due dates will be posted on the Schedule page.
  • Assignments are due at the beginning of class on the indicated dates.

No late assignments are accepted under any circumstances.

Assignments will be graded along the following lines:

  • 0 = NG = didn't do anything
  • 1 = incomplete or mostly incorrect.
  • 2 = more or less incorrect but you are on the right track; or correct but is muddled in the argument.
  • 3 = correct logic and written coherently. Might have a missing step or two.
  • 4 = wow! I think you really get it.

Note that strong effort as you get better will make up for poorer performances in previous weeks. Full solutions to all problems will be posted on the Schedule page after they are handed in.

In computing the final grade, the two lowest assignment grades will be dropped, thus allowing for the occasional catastrophe that interferes with handing an assignment in on time.

PLEASE NOTE: Neatness counts! Two points (on the 0-4 scale) will be automatically deducted from any assignment that does not meet the following requirements:

  • Staple sheets together in the top left corner.
  • Put your name and the assignment number / page number at the top right corner of all pages–e.g., “Assn. 1/1”, “Assn. 1/2”, etc.
  • Indicate your final solution clearly.
  • Show all the steps used to arrive at your solution.
  • Write legibly.
  • Hand in clean copy–i.e., don't hand in messy work where bits have been crossed out, etc.
  • Do not hand in paper with frayed edges torn from a notebook.
  • Hand in assignments on 8“x11” lined paper.

You are strongly encouraged to hand in assignments produced using the typesetting language LaTeX. To get started, you can reference Getting Started with Latex, go to this list of LaTeX tutorials, or simply enter “latex tutorial” in Google to see many other links. A LaTeX assignment template is also available, and LaTeX versions of the assignments will be posted.


Three exams will be scheduled during the semester. Each will cover lectures and readings from the course segment immediately preceding the exam, but the last may also cover earlier material. The first two exams will be take-home exams; the third exam will be scheduled for an agreed-upon time outside of class time. Exams are graded on a 100 point scale.

Note that you are responsible for all assigned readings (see the Schedule page), whether or not the material is covered in lectures.

Academic accommodations are available for students with documented disabilities. Please schedule an appointment with the instructor early in the semester to discuss any accommodation that may be needed for the course. All accommodations must be approved through the Office of Disability and Support Services (ext. 7584) as indicated in their accommodation letter.