 |
600.471
Theory of Computation |
|
|
|
Susan Hohenberger's office hours are by appointment. Venkata Ponnam's office hours are Tuesdays, 11:30-12:30 in Wyman 416.
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 alternate 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) 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: 30%
- Quizzes: 60%
- Participation in class: 10%
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:
- Start Early. Most problems will not be hard, but some will be. Difficult problems are not typically solved in one sitting. Start early and let the ideas come to you over the course of a few days.
- Be rigorous and concise. We expect real proofs and real analyses, at the level of rigor in the textbook. Express your ideas at the proper level of detail. Most solutions require a few paragraphs at the most. Take some time to think over the clearest way to express your thoughts before you start writing.
- Acknowledge known errors. More credit will be given for solutions with errors or gaps in proofs when these problems are explicitly pointed out by the student. This tells us that you understood there was a problem, even if you did not know how to fix it. When errors are not acknowledged, we will assume they were not recognized.
- Typing? We recommend that all problem set solutions be typed up using LaTeX. However, we will accept neatly hand-written solutions and hand-drawn diagrams. If we can't read it, no credit will be given.
- Collaboration? You are encouraged to solve all the homework questions on your own, but are permitted to brainstorm difficult problems in small groups, as long as each of you writes the solutions individually and honestly acknowledges the cooperation. Needless to say, if you work with others but never come up with the solution on your own, you may do okay in the homework component of your grade, but you will suffer on exams, so be careful.
- Cheating? More or less, you are only allowed to use the textbook, your lecture notes and discussions with classmates to help you solve the problem sets. In particular, the use of the internet, course bibles, outsiders, and other clearly "cheating" resources is strictly prohibited. Please talk to me if you are having problems keeping up with the material.
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