CIS 262: Automata., Computability, and Complexity

CIS 262: Automata, Computability, and Complexity
Fall 2011, 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 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

Class: Tues and Thurs 12--1.30, Berger Auditorium, Skirkanich Hall
Instructor: Rajeev Alur (alur@cis), Office hour: Wed 3 -- 4 (Levine 609)
Teaching Assistants:
- Loris D'Antoni (lorisdan@seas); Office hour: Tue 4 -- 5; Levine 612
- Charles Kong (ckong@seas); Office hour: Wed 1.30 -- 2.30; Skirkanich 508
- Salar Moarref (moarref@seas); Office hour: Mon 1.30 -- 2.30; Levine 512
- Mukund Raghothaman (rmukund@seas); Office hour: Mon 3 -- 4; Levine 612
Recitation: Monday 4.30 -- 5.30 Berger Auditorium, Skirkanich Hall
Pre-requisites: CIS 160

Textbooks

Required: Introduction to the theory of computation, Michael Sipser, Thomson Course Technology, Second Edition, 2004.
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

Homework Assignments: One third
Two Midterms: One third
Final Exam: One third

Handouts

Handouts are posted on the Blackboard site for the course.

Tentative Schedule

Sept 8: Course logistics, Discussion of course content, Introduction to automata
Sept 13, 15, 20, 22, 27, 29; Oct 4, 6: Finite automata and regular languages (Chapter 1)
Oct 13: Midterm 1
Oct 18, 20, 25, 27; Nov 1, 3, 8, 10: Turing machines and undecidability (Chapters 3, 4, 5)
Nov 15: Midterm 2
Nov 17, 22, 29; Dec 1, 6, 8: Complexity classes and NP-completeness (Chapter 7)
Dec 15, 12 - 2, Final Exam

Notes

Compared to the last couple of years, we are making some changes: we are using a different textbook, and we are skipping the topic of "context-free grammars" to allow more in-depth coverage of computability and NP-completeness.
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 Brittany Binler in Levine 311 (binler@seas). Best time to pick up graded material is either 9.30 -- 10.30am or 3 -- 4pm on Mondays and Wednesdays.
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