600.271: Automata and Computation Theory

Course Information


Instructor Info


Exam Dates

TA and CAs




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:

Reading Material


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