CS 542 Theory of Computation
Spring 1999

Brief Description. This course will be an introduction to the theory of computational complexity. Most of the course will be based on Part Three of the textbook which includes the following topics: time complexity, NP-completeness, space complexity, the hierarchy theorems, relativization, circuit complexity, approximation algorithms, probabilistic algorithms, alternation, interactive proofs systems, parallel computation and cryptography. Additional topics in computability theory (from Chapter 6 of the textbook) and in small-depth circuit complexity may be covered.

Instructor. Alexis Maciel
Office: Science Center 379
Phone: 268-2385
E-mail: alexis@clarkson.edu.

Office Hours. Monday and Wednesday 11:00--12:00, Tuesday and Thursday 10:00--11:30, and by appointment.

Required Text.

    Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, Boston, MA, 1997.

Grading.

Homework assignments 50%
One test 15%
Final exam 35%

The assignment policy for the course will be stated on the first assignment. Tentative date for the test: March 10.