Fall 2013, University of Pennsylvania

- Class: Tues and Thurs 12--1.30, Towne 100, Heilmeier Hall
- Instructor: Rajeev Alur (alur@cis), Office hour: Wed 4 -- 5 (Levine 609)
- Teaching Assistants:
- Atai Barkai (abarkai@sas); Office hour: Wed 5.30 -- 6.30, Moore 100
- Danica Bassman (danicab@wharton); Office hour: Mon 11-12, Moore 100
- Adam Freilich (adam.m.freilich@gmail.com); Office hour: Wed 10--11, Moore 100
- Rafe Kettler (rkettler@seas); Office hour: Wed 2--3, Moore 100
- Robert Rand (rrand@seas); Office hour: Mon 6--7, Towne 313

- Recitation: Monday 4.30 -- 5.30, Levine 101, Wu & Chen Auditorium
- Pre-requisites: CIS 160

- Required: Introduction to the theory of computation, Michael Sipser, Third Edition, 2012, or Second Edition, 2006.
- Additional reference: Introduction to Automata Theory, Languages and Computation, J.E. Hopcroft, R. Motwani, and J.D. Ullman, Addison Wesley, Third edition, 2006.

- Weekly Homework Assignments (12 total): One third
- Two Midterms: One third
- Final Exam: One third

- Aug 29: Course logistics, Discussion of course content, Introduction to automata
- Sept 3, 5, 10, 12, 17, 19, 24, 26: Finite automata and regular languages (Chapter 1)
- Oct 1: Midterm 1
- Oct 3, 8, 15, 17, 22, 24, 29, 31; Nov 5: Turing machines and undecidability (Chapters 3, 4, 5)
- Nov 7: Midterm 2
- Nov 12, 14, 19, 21, 26; Dec 3, 5, 10: Complexity classes and NP-completeness (Chapters 7 and 8)
- Dec 18, 12 - 2: Final Exam, Towne 100

- Homework 1
- Homework 2; Solutions
- A note on proving correctness of automata constructions
- Homework 3, Solutions
- Homework 4, Solutions
- A note on DFA minimization
- Preparing for Midterm 1
- Midterm 1, 2010; Solutions
- Midterm 1, 2011; Solutions
- Midterm 1; Solutions
- Homework 5, Solutions
- Homework 6, Solutions
- Homework 7; Solutions
- Preparing for Midterm 2
- Midterm 2, 2011; Solutions
- Midterm 2, See Piazza for solutions
- Homework 8, Solutions
- Homework 9; Solutions
- Homework 10, Solutions
- Preparing for Final Exam

- We will use Piazza for discussions.
- Grades are posted on canvas.
- During the class, use of mobile devices and laptops is prohibited.
- Recitation: During Monday's recitation, we will mainly focus on solving problems. Many students find the homeworks difficult, and even when they have solved the problem, some find it difficult to write the answer concisely and rigorously. Recitation should help with these challenges. However, attendance for recitation is optional as no new material will be covered.
- Homework Drop-off and Pick-up: On the day the homework is due, it should be submitted before the lecture starts. Graded exams and homeworks can be collected from Laura Fox in Levine 308 (lffox@seas).
- Plagiarism Policy: For homeworks, 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 reported to the Office of Student Conduct at Penn. Start working on homework problems early, and if you get stuck, contact one of us; we will be happy to help you progress.

Maintained by Rajeev Alur