### 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. |