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




Grades will be based on


Maintained by Rajeev Alur