Formal models of computation: finite automata and Turing machines. Universality Theorem and 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.
This 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:30pm-2:50pm, Room CS302.
Office hours: MW 3-4pm.
Teaching Assistant: Yefim Shuf, 412 CS Building, 8-3946. yshuf@cs
Office hours: Wed 10-11:30am.
Mondays 4-5pm in Room 402. These will usually be held every other week.
Last modified 11/12/98, by Sanjeev Arora