Fall 2020, University of Pennsylvania

- Lectures will be pre-recorded. Zoom sessions for review and problem solving: Tues/Thurs 12-1.20.
- Instructor: Rajeev Alur (alur@cis)
- Teaching Assistants:
- Alan Ismaiel (head TA) (aismaiel@seas)
- Alexander Kassouni (kassouni@seas)
- Austen Li (austenli@wharton)
- Batchema Sombie (batchema@sas)
- Chanseo Bae (cbae@wharton)
- Christopher Yin (ctyin@seas)
- Francesca Marini (fmarini@sas)
- Hannah Lord (hlord@seas)
- Khye Facey-Marshall (khyefac@seas)
- Kyven Wu (kyven@seas)
- Paula Scanlan (pscanlan@seas)
- Vignesh Valliyur (vigneshv@sas)

- Pre-requisites: CIS 160
- Canvas for lecture recordings, homeworks, and course handouts
- Gradescope for submission of homeworks and exams
- Piazza for course-related discussion

- Required: Introduction to the theory of computation, Michael Sipser, Third Edition, 2012
- 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 (due Thursday evenings): 12 total, 10 pts each, highest 10 scores scaled up to 120 pts total
- Two Midterms: 50 pts each
- Final Exam: 80 pts

- Sept 1: Course logistics and preview of course content
- Sept 3: Virtual get to know your professor, teaching assistants, and classmates
- Part A: Finite automata and regular languages (Chapter 1)
- Sept 4: Lectures A1 (Deterministic Finite Automata), A2 (DFA Correctness), homework 1 (due 9/10) available online
- Sept 8, 10: Review of lectures A1/A2, and problem solving
- Sept 11: Lectures A3 (DFA Lower bounds), A4 (Nondeterministic Finite Automata), homework 2 (due 9/17) available online
- Sept 15, 17: Review of lectures A3/A4, and problem solving
- Sept 18: Lectures A5 (Operations on regular languages), A6 (Regular expressions), homework 3 (due 9/24) available online
- Sept 22, 24: Review of lectures A5/A6, and problem solving
- Sept 25: Lectures A7 (Proving non-regularity), A8 (Decision problems), homework 4 (due 10/1) available online
- Sept 29, Oct 1: Review of lectures A3/A4, problem solving, and midterm review
- Oct 6: Midterm 1

- Oct 8: Virtual 262 Social
- Part B: Turing machines and undecidability (Chapters 3, 4, 5)
- Oct 9: Lectures B1, B2 (Turning Machines) homework 5 (due 10/15) available online
- Oct 13, 15: Review of lectures B1/B2, and problem solving
- Oct 16: Lectures B3 (TM variants), B4 (Decidability and Recognizability), homework 6 (due 10/22) available online
- Oct 20, 22: Review of lectures B3/B4, and problem solving
- Oct 23: Lectures B5 (Undecidability), B6 (Unrecognizability), homework 7 (due 10/29) available online
- Oct 27, 29: Review of lectures B5/B6, and problem solving
- Oct 30: Lectures B7, B8 (Reduction proofs), homework 8 (due 11/5) available online
- Nov 3, 5: Review of lectures B7/B8 and problem solving
- Nov 10: Midterm Review
- Nov 12: Midterm 2

- Part C: Complexity classes and NP-completeness (Chapters 7 and 8)
- Nov 13: Lectures C1, C2, homework 9 (due 11/19) available online
- Nov 17, 19: Review of lectures C1/C2, and problem solving
- Nov 20: Lecture C3, homework 10 (due 11/25) available online
- Nov 24: Review of lecture C3, and problem solving
- Nov 25: Lectures C4, C5, homework 11 (due 12/3) available online
- Dec 1, 3: Review of lectures C4/C5, and problem solving
- Dec 4: Lectures C6, C7, homework 12 (due 12/10) available online
- Dec 8, 10: Review of lectures C6/C7 and problem solving

- Final Exam: Wed, Dec 16, Noon-2pm

Maintained by Rajeev Alur