600.271: Automata and Computation Theory
Course Information
Meetings
- Lectures: Tuesday and Thursday, 1:30-2:45 PM, Shaffer 303
- Voluntary Help Classes: Tuesday and Wednesday, 3:30-4:30 PM, NEB 215, led by the instructor
Instructor Info
- Instructor: S. Rao Kosaraju
- Office: NEB 212
- Office Hours: unlimited access
- Phone Number: x6-8134
- Email: kosaraju@cs.jhu.edu
Grading
- One assignment per week (20% of the grade) (the lowest score will be dropped)
- Two midsemester examinations (25% of the grade per exam)
- Final examination (30% of the grade)
Exam Dates
- First midsemester examination: Tuesday, 03/12/2013
- Second midsemester examination: Thursday, 04/18/2013
- Final examination: Monday, 05/13/2013, 2-4:30 PM
TA and CAs
TA
- Darcey Riley
- darcey.riley@gmail.com
- Office: Hackerman 321
- Office Hours: Monday and Wednesday, 1:30-2:30 PM
CAs
- Austin Estep (aje@jhu.edu)
- Chandler Furman (chandler.furman@gmail.com)
- Matt Molisani (mmolisa2@jhu.edu)
- Lavanya Sivakumar (lavanya@jhu.edu)
- Justin Snyder (jsnyde32@jhu.edu)
Topics
The course emphasizes design aspects rather than detailed proofs of correctness. Of course, you need to be able to argue precisely
when we cover topics such as pumping lemmas, the right congruence lemma, reductions, and polynomial time reductions. The major
topics to be covered are:
- Design of finite automata, pushdown automata, linear bounded automata, Turing machines
- Pumping lemmas for finite automata and pushdown automata
- Right congruence lemma for finite automata
- Regular expressions
- Design of grammars (emphasis on context-free grammars)
- Correspondence between automata and grammars (not too many proofs)
- Computable problems
- Recursive and recursively enumerable sets
- Decision problems
- Halting problem
- Undecidability via reduction (emphasis on m-reduction)
- Rice's Theorem
- P and NP classes (equivalence between two notions of NP)
- NP-completeness, polynomial time reduction
Reading Material
- Class Notes (primary source)
- M. Sipser: Introduction to the Theory of Computation, Thomson Course Technology
- H.R. Lewis and C.H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall
Assignments
For each homework, each subproblem is graded separately out of 10 points. At the end of the semester, all the homeworks will be
scaled to have equal weights.
Each week, the 5 CAs and 1 TA will divide all the homeworks up into six groups. Each CA/TA will grade one group. In order to
ensure fairness, we will rotate the groups each week. Groups are determined by your last name. Group 1: A-D. Group 2: F-H.
Group 3: J-L. Group 4: M-P. Group 5: R-S. Group 6: T-Z. The CAs/TA also have numbers: 1 = Austin Estep, 2 = Chandler Furman,
3 = Matt Molisani, 4 = Lavanya Sivakumar, 5 = Justin Snyder, 6 = Darcey Riley.
In order to figure out who graded your homework, you can use the following formula: your group + HW# = CA# (mod 6). For instance,
if your last name starts with M, then Assignment 2 was graded by Darcey. (The exception is that CAs cannot grade their friends'
homeworks, so if you are friends with the CA, then your homework was graded by Darcey.) If you have a question about the grading
of your homework, please email Darcey or come to her office hours, instead of contacting the grader directly.
We sometimes accept homeworks a day or two late. However, if you turn your homework in late, Darcey will grade it herself instead
of distributing it to the appropriate CA. Darcey is the harshest grader.
Exam Review Material