CIS 262: Automata, Computability, and Complexity
Fall 2020,
University of Pennsylvania
Introduction
This course offers an introduction to the science behind computing by
studying computation abstractly without worrying about specifics of programming
languages and/or computing platforms.
In particular, we will study
(a) finite automata that capture what can be computed using constant
memory, and define the class of regular languages useful for pattern matching
languages;
(b) the universal computational model of
Turing machines, and the inherent
limits of what can be solved on a computer (undecidability), and
(c) the notion of computational tractability (which problems
can be solved in polynomial-time),
and the million-dollar P vs NP question.
The course also emphasizes rigorous thinking and mathematical proofs.
Logistics
- Lectures will be pre-recorded. Zoom sessions for review and problem solving: Tues/Thurs 12-1.20.
- Instructor:
Rajeev Alur
(alur@cis)
- Teaching Assistants:
- Pre-requisites: CIS 160
- Canvas for lecture recordings, homeworks, and course handouts
- Gradescope for submission of homeworks and exams
- Piazza for course-related discussion
Textbooks
-
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.
Grading
Grades will be based on
- 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
Schedule
- 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