CSG714: Theory of Computation
Class meeting times/location: 433 Ryder
Office Hours: T 3:30-4:30, Th 4:00-5:00
Course Description This course provides a
graduate-level introduction to the theory of computation. We
will study models of computation, decidability, space and time
complexity classes, NP-completeness, probabilisitic complexity,
interactive proof systems, probabilistically checkable proofs, the
recursion theorem, and other advanced topics in computability and
complexity theory. For more details, see the class schedule.
60% of the material covered in the course is present in both texts,
20% only in Sipser's text, and 20% only in Kozen's text. For more
details, see the class schedule.
Two other useful reference books may be the following:
Introduction to Automata Theory, Languages, and Computation,
J. Hopcroft, R. Motwani, and J. Ullman, Addison Wesley, 2nd Edition,
Models of Computation: Exploring the Power of Computing, by
The course grade will be based on six problem sets
(total 40%), a midterm (25%), a final
exam (30%), and class participation
Problem sets are due at the beginning of class. No late submission would be accepted.
Students may discuss the problem sets with one another, but solutions
should be written up separately. If a key idea is
obtained from another person (other than the instructor) or from
book or paper (other than the course textbook), then the source of that
idea should be cited. Solutions should be presented in a clear
Each week, a ``Problem of the Week'' (or two) will be handed out,
a student will be called on to present his/her solution to the problem
in the following week. Everbody is required to present at least once
the course. The grade for class participation will be based on
quality of the presentation and participation in class discussions.
The midterm and the final will both be take-home exams -- dates to be