**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:**S. Rao Kosaraju**Office:**NEB 212**Office Hours:**unlimited access**Phone Number:**x6-8134**Email:**kosaraju@cs.jhu.edu

- 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)

**First midsemester examination:**Tuesday, 03/12/2013**Second midsemester examination:**Thursday, 04/18/2013**Final examination:**Monday, 05/13/2013, 2-4:30 PM

- Darcey Riley
- darcey.riley@gmail.com
- Office: Hackerman 321
- Office Hours: Monday and Wednesday, 1:30-2:30 PM

- 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)

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

- 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

- Assignment 1 (Solutions)
- Assignment 2 (Solutions)
- Assignment 3 (Solutions)
- Assignment 4 (Solutions)
- Assignment 5 (Solutions)
- Assignment 6 (Solutions)
- Assignment 7 (Solutions)
- Assignment 8 (Solutions)
- Assignment 9 (Solutions)

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.

Last edited 02/19/2013.