General Information |
Final Exam |
Formal models of computation: finite automata and Turing machines.
Universality Theoremand the Church-Turning Thesis. Computability Theory
("What can or cannot be computed?") and Complexity Theory ("How
efficient can a certain computation be?"). NP-completeness and PSPACE-
completeness. An introduction to complexity issues in application areas such
as robotics, graphics, compilers, and computer security. Prerequisites: COS 341.
Lectures: MW 1:30-2:50, Room:
Professor: Richard J. Lipton -
311 CS Building - 258-4646
Tina McCoy -
410 CS Building - 258-1746