CSG714: Theory of Computation

Spring 2008

Instructor:  Rajmohan Rajaraman

Class meeting times/location:     433 Ryder

Office Hours:    T 3:30-4:30, Th 4:00-5:00

Course Description



Tentative Course Schedule

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.

Recommended Textbooks

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:


The course grade will be based on six problem sets (total 40%), a midterm (25%), a final exam (30%), and class participation (5%).

Problem Sets

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 another book or paper (other than the course textbook), then the source of that idea should be cited.  Solutions should be presented in a clear and concise manner.  

Class Participation

Each week, a ``Problem of the Week'' (or two) will be handed out, and 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 during the course.  The grade for class participation will be based on the quality of the presentation and participation in class discussions.


The midterm and the final will both be take-home exams -- dates to be determined.