 |
600.471
Theory of Computation |
|
|
|
(Thanks to Nancy Lynch and Ronald L. Rivest for donating materials for this course.)
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.
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
NP-completeness, 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) bi-weekly problem sets, three
in-class quizzes, and a final exam. The final grade will be
computed using the following weights:
- Problem Sets: 30%
- Quizzes: 30%
- Final Exam: 30%
- Participation in class: 10%
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.
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.
There will be three quizzes and one final exam. The quizzes will be held during class time on
- Monday, Oct 1;
- Monday, Oct 29;
- Monday, Dec 3.
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