CIS 262: Automata, Computability, and Complexity
Fall 2009,
University of Pennsylvania
Introduction
This course offers an introduction to the science behind computing by
stuying 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 give the class of regular languages useful for pattern matching
languages;
(b) context-free grammars that faciliate declarative specifications of language
syntax, and the associated operational model of pushdown automata;
(c) the universal computational model of
Turing machines, and the inherent
limits of what can be solved on a computer (undecidability), and
(d) 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
- Class: Tues and Thurs 12--1.30, Berger Auditorium, Skirkanich Hall
- Instructor:
Rajeev Alur
(alur@cis), Office hour: Wed 4-5 (Levine 609)
- Teaching Assistants:
- Recitation: Monday 4.30 -- 5.30 LRSM Auditorium
- Pre-requisites: CIS 160
Textbooks
- Required: Introduction to Automata Theory, Languages
and Computation, J.E. Hopcroft, R. Motwani,
and J.D. Ullman, Addison Wesley, Third edition, 2006.
-
Additional Reference: Introduction to the theory of computation, Michael
Sipser, Thomson Course Technology, Second Edition, 2004.
Occasionally, we will cover some topics not discussed in the text, or present a
topic in a manner significantly different compared to the text.
In such acases, course notes will be distributed in class and posted on this page.
Grading
Grades will be based on
- Six Homework Assignments: One third
- Two Midterms: One third
- Final Exam: One third
Tentative Schedule
- Sept 10: Course logistics, Discussion of course content, Introduction to
automata
- Sept 15, 17, 22, 29 (note: no lecture on Sept 24); Oct 1, 6, 8: Finite
automata and regular languages (Chapters 1 -- 4)
- Oct 13: Midterm 1
- Oct 15, 20, 22, 27, 29; Nov 3, 5: Pushdown automata and context-free
languages (Chapters 5 -- 7)
- Nov 10: Midterm 2
- Nov 12, 17, 19, 24; Dec 1: Turing machines and undecidability (Chapters 8, 9)
- Dec 3, 8, 10: NP-completeness (Chapter 10)
Notes
- 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 homeworks and exams will be available with Merissa Mele (Levine 311).
- 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