CSG714: Theory of Computation

Spring 2009

Instructor: Rajmohan Rajaraman

Class meeting times/location: TuF 3:25 PM-5:05 PM, 5 Snell Library

Office Hours: TuF after class

Course Description

Textbook

Grading

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.

Grading

The course grade will be based on 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.

Exams