Formal models of computation: finite automata and Turing machines. Universality Theorem and the ChurchTuring Thesis. Computability Theory ("What can or cannot be computed?") and Complexity Theory ("How efficient can a certain computation be?"). NPcompleteness and PSPACEcompleteness. An introduction to complexity issues in application areas such as robotics, graphics, compilers, and computer security.

Fall 2012
Lectures: Monday,Wednesday, 1:302:50
