Theory of Computation

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

Office Hours

TA Rebecca Shapiro's office hours are every Wednesday from 10:30-11:30am in the SPAR lab of Wyman Park Building. Susan Hohenberger's office hours are by appointment.

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

Problem Sets

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. 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: Friday, June 13, 2008