Theory of Computation

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

(Thanks to Nancy Lynch and Ronald L. Rivest for donating materials for this course.)

Office Hours

Omar Zaidan's office hours are Tuesdays 10-11 and Thursdays 12-1 in the CS undergrad lab (NEB 225/227). Susan Hohenberger's office hours are by appointment.


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.

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 alterate 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) bi-weekly problem sets, three in-class quizzes, and a final exam. The final grade will be computed using the following weights:

Problem Sets

Problem sets will be due approximately every two weeks. However, when computing your grade at the end of the course, we will drop your lowest score. Therefore you need not worry about getting a bad grade on a single assignment.

With regards to problem sets: full credit will be given for correct answers and proofs. We will also grant partial credit for partial solutions and solutions with minor flaws. We will also give a small amount of partial credit for answers which read in full, "I don't know." Likewise, proofs with gaps will receive partial credit, and the partial credit granted will increase if the gaps are explicitly noted. We will give no credit for wildly incorrect answers which are obviously only there in the hopes of getting partial credit. Please only write down answers in which you are confident.

We recommend that all problem set solutions be typed up. However, we will accept neatly hand-written solutions and hand-drawn diagrams.

Collaboration Policy

We strongly encourage collaboration on problem sets. We do not expect you to be able to solve every problem on your own. We do, however, expect you to write up your own solution to every problem even if the solution is the result of a collaborative effort. To repeat: each person must write up their solutions separately. Also, in your write-up please credit the people with whom you worked. If you consult any reference material, please note which sources you used for each problem.

Quizzes and Exams

There will be three quizzes and one final exam. The quizzes will be held during class time on Each quiz will cover a unit of the course; the final exam will be cumulative. The final has yet to be scheduled. All exams are open book; bring your course textbook with you.
Last modified: Monday, October 8, 2007