Theory of Computation

Course Home Page
General Information/Policies
Course Materials by Lecture Date

Office Hours

Susan Hohenberger's office hours are by appointment. Venkata Ponnam's office hours are Tuesdays, 11:30-12:30 in Wyman 416.

Prerequisites and 600.271

This is an introductory graduate course on the theory of computation. At its heart, this is a mathematics course. We assume that you have taken a prior course in discrete mathematics and are comfortable with writing formal mathematical proofs.

If you are a Hopkins undergraduate, note that you cannot get credit for both 600.271 and 600.471. You can, however, choose to take either course to satisfy your requirement.

Course materials

The book for this class is Introduction to the Theory of Computation (2nd Edition) by Michael Sipser. If you do not have a copy of the textbook, copies are available for purchase at the Johns Hopkins University Bookstore.

An errata exists for this second edition.

The textbook has been placed on reserve at the MSE Library (Building 19), as well as three other books that students may wish to consult for an alternate explanation:

Check the course website and/or email the TA to receive extra copies of handouts and supplemental readings.

Course Mailing List

The mailing list is cs471[ignore this spam break]@cs.jhu.edu.

Grading Policy

There will be (approximately) five problem sets, three in-class quizzes, and a final exam. The final exam is optional. A grade will be calculated for you based on the below formula during the last week of class. You may choose to accept this grade and not attend the final exam, or you may choose to take the final exam and you will then receive the higher of the two grades. The pre-final exam grade will be computed using the following weights:

Problem Sets

Some of the homework exercises will be routine, but others will be more challenging. I do not expect you to solve all of the homework problems, but I hope that you will benefit from working on the more difficult ones. A few hints on homework:

Quizzes and Exams

There will be three quizzes and one final exam. To each test, you may bring your course textbook and any notes taken during lecture. Other textbooks and outside notes are strictly prohibited. The quizzes will be held during class time. Each quiz will cover a unit of the course; the final exam will be cumulative.
Last modified: Monday, July 20, 2009