CIS 511: Theory of Computation.
Spring 2008, University of Pennsylvania

Logistics

• Class: Tues Thurs 12--1.30, Towne 313
• Instructor: Rajeev Alur (alur@cis), Office hour: Wed 4.30-5.30 (Levine 609)
• Teaching Assistant: Zhuowei Bao zhuowei@seas, Office hour: Mon noon-1.00 (Levine 575)

Textbooks

• Required: Introduction to Automata Theory, Languages and Computation, J.E. Hopcroft, R. Motwani, and J.D. Ullman, Addison Wesley, Third edition, 2007.
• Additional Reference: Introduction to the theory of computation, Michael Sipser, Second Edition, 2006, Thomson Course Technology

Handouts

• Homework 1, Due Feb 5.
• Solutions to Homework 1.
• Notes on tree automata.
• Homework 2, Due Feb 19.
• Solutions to Homework 2.
• Homework 3, Due March 4.
• Solutions to Homework 3.
• Practice Midterm (from 2007)
• Midterm
• Midterm Solutions
• Homework 4, Due April 1.
• Solutions to Homework 4.
• Homework 5, Due April 24.

Grading

• Homework Assignments (5) 50%
• Midterm 20 %
• Final Exam 30%

Tentative Schedule

• Jan 17,22,24,29,31; Feb 5,7: Finite automata and regular languages
• Feb 12,14,19,21,26,28; March 4: Pushdown automata and context-free languages
• March 6: Midterm
• March 11,13,25,27; April 1,3,8: Turing machines, computability, and Undecidability
• April 10,15,17,22,24,29: NP-completeness and complexity theory
• Final Exam: Wed, May 7, noon - 2pm

Notes

• We will assume that everyone has taken an undergraduate course on automata theory. Hence, we will quickly review the basics in finite automata and pushdown automata, and focus on more advanced concepts.
• While we will follow the text closely, we will have excursions into related topics such as automata over infinite words, tree automata, ordered binary decision diagrams, and nested word automata. These topics have interesting applications to my research which centers on tools for formal modeling and analysis of systems.
• Homework submissions and pickup: Homeworks should be given to, and graded homeworks and exams should be collcted from, Kamila Mauro (311 Levine).
• Late homework policy: Homeworks will be due on Tuesdays. You can submit the homework 2-days late (on Thursday), but we will deduct 20% of your marks as a penalty. Further extensions will not be permitted.
• Plagiarism Policy: For homeworks and exams, you can use your class notes, the textbook, and the reference book, but not old solutions, friends, other books, or any other material from the web. For violations of this rule, you will be given zero credit for that assignment.
• WPE-1: The final exam will be used to evaluate PhD students for WPE-1 requirement. While WPE-1 pass is based solely on the final exam (and students may attempt WPE-1 without registering for 511), the grade for the course is based on overall performance as indicated above.