
600.471 Theory of Computation 


TA Rebecca Shapiro's office hours are every Wednesday from 10:3011:30am in the SPAR lab of Wyman Park Building. 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.
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.
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:
 Introduction to Languages and the Theory of
Computing, John Martin
 Automata and Computability, Dexter Kozen
 Computers and intractability : a guide to the theory of
NPcompleteness, Michael Garey and David S. Johnson.
Check the course website and/or email the TA to receive extra copies of handouts and supplemental readings.
The mailing list is cs471[ignore this spam break]@cs.jhu.edu.
There will be (approximately) five problem sets, three
inclass quizzes, and a final exam. The final grade will be
computed using the following weights:
 Problem Sets: 25%
 Quizzes: 30%
 Final Exam: 35%
 Participation in class: 10%
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 handwritten solutions and handdrawn diagrams.
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 writeup
please credit the people with whom you worked.
If you consult any reference material, please note which sources
you used for each problem.
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