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


Textbooks


Grading

Grades will be based on

Schedule


Handouts


Notes


Maintained by Rajeev Alur