COS 487

Directory
General Information | Schedule and Readings | Assignments | Handouts | Interesting Links

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.

General Information

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.

The issues studied in this course constitute the logical foundations of computer science. Time permitting, we will explore how they touch upon current areas of research, including AI, robotics, computer security and cryptography, and computation using quantum devices.

Both grads and undergrads are welcome to take the course. Some minimal level of mathematical sophistication will be assumed; COS 341 (or an equivalent course) is adequate preparation. 50% of the grade will be based upon assignments, which will be handed out every two weeks. There will be two exams, which will be open-book and take-home.

The text will be Theory of Computation by Michael Sipser, printed by PWS publishing. Here is its errata list.

New this term: Biweekly precepts to help students with the assignments.

Lectures: M,W at 1:30pm-2:50pm, Room CS302.

Professor: Sanjeev Arora, 307 CS Building, 258-3869, arora@cs

                Office hours: MW 3-4pm.

Teaching Assistant: Yefim Shuf, 412 CS Building, 8-3946. yshuf@cs

                Office hours: Wed 10-11:30am.

Precepts: 

Mondays 4-5pm in Room 402. These will usually be held every other week.

Last modified 11/12/98, by Sanjeev Arora