CIS 262: Automata, Computability, and Complexity
Fall 2018,
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 polynomialtime),
and the milliondollar P vs NP question.
The course also emphasizes rigorous thinking and mathematical proofs.
Logistics
 Class: Tues and Thurs 121.20, Towne 100, Heilmeier Hall
 Instructor:
Rajeev Alur
(alur@cis), Office hour: Wed 45, Levine 609
 Teaching Assistants:
 Pritam Choudhury (pritam@seas), Office hour: Wed 34, Levine 6th floor
 Kurt Convey (kconvey@seas), Office hour: Wed 78, Levine 6th floor
 Nate Fessel (fesseln@sas), Office hour: Mon 34, Levine 6th floor
 Kishor Jothimurugan (kishor@seas), Office hour: Mon 56, Levine 6th floor
 Seyoung Kim (seyoungk@seas), Office hour: Mon 45, Levine 6th floor
 Soloman Maina (smaina@seas), Office hour: Mon 121, Levine 6th floor
 Andrew Martin (andrmar@sas), Office hour: Wed 23, Levine GRW 5th Floor
 Xuan Ru Ng (xng@seas), Office hour: Tues 56, Levine GRW 5th Floor
 Recitation: Monday 23, Towne 100
 Prerequisites: CIS 160
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: 12 total, 10 pts each, 10 best scores contribute to course grade
 Two Midterms: 50 pts each
 Final Exam: 100 pts
Schedule
 Aug 28: Course logistics and preview of course content
 Aug 30, Sept 4, 6, 11, 13, 18, 20, 25: Finite
automata and regular languages (Chapter 1)
 Sept 27: Midterm 1 (in class)
 Oct 2, 9, 11, 16, 18, 23, 25, 30, Nov 1: Turing machines and undecidability (Chapters 3, 4, 5)
 Nov 6: Midterm 2 (in class)
 Nov 8, 13, 15, 20, 27, 29; Dec 4, 6: Complexity classes and NPcompleteness (Chapters 7 and 8)
 Dec 20, 12  2: Final Exam
Notes
 We will use Piazza for discussions.
Homeworks, lecture slides, and handouts will be posted on Piazza.
 For homework submission and grading, we will use Gradescope
 For a few problems, we will use the tool AutomataTutor.
Sign up for an account on AutomataTutor, make sure that name and email on this account matches your Penn account.
 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.
 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