CIS 262: Automata, Computability, and Complexity
University of Pennsylvania
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
(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.
- Class: Tues and Thurs 12--1.20, Towne 100, Heilmeier Hall
(alur@cis), Office hour: Wed 4 -- 5 (Levine 609)
- Teaching Assistants:
- Recitation: Monday 4.30 -- 5.30, DRLB A1
- 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.
Grades will be based on
- Weekly Homework Assignments: 10 total, 10 pts each
- Two Midterms: 50 pts each
- Final Exam: 100 pts
- Aug 27: Course logistics, Discussion of course content, Introduction to
- Sept 1, 3, 8, 10, 15, 17, 22, 24: Finite
automata and regular languages (Chapter 1)
- Sept 29: Midterm 1 (in class)
- Oct 1, 6, 13, 15, 20, 22, 27, 29; Nov 3: Turing machines and undecidability (Chapters 3, 4, 5)
- Nov 5: Midterm 2 (in class)
- Nov 10, 17, 19, 24; Dec 1, 3, 8: Complexity classes and NP-completeness (Chapters 7 and 8)
- Dec 18, 12 - 2: 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
- 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.
- Open book exams: Both midterms and final exam will be open book: during the exam, you can consult
the textbook, your class notes, and handouts distributed during the course, but are not allowed to
access the internet.
Maintained by Rajeev Alur