COS 487 

Directory Formal models of computation: finite automata and Turing machines. Universality Theorem and the ChurchTurning 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.Prerequisites COS 341. General InformationThis objective in this course is to study two kinds of questions at a theoretical
level. First, what computations can be performed on a computer? (This is the subject of
computability theory .) Second, how efficiently can they be performed? (This is the
subject of complexity theory .) These questions will ultimately be studied with respect to
an idealized model of the computer, namely, the Turing machine. But we will start off by
studying weaker models of computation: finite automata and grammars. New this term: Biweekly precepts to help students with the assignments.
Lectures: M,W at 1:30pm2:50pm, Room CS302.Professor: Sanjeev Arora, 307 CS Building, 2583869, arora@cs Office hours: MW 34pm. Teaching Assistant: Yefim Shuf, 412 CS Building, 83946. yshuf@cs Office hours: Wed 1011:30am.
Precepts:Mondays 45pm in Room 402. These will usually be held every other week.
Last modified 11/12/98, by Sanjeev Arora
