CSG714: Theory of Computation
Spring 2009
Instructor: Rajmohan
Rajaraman
Class meeting times/location:
TuF 3:25 PM5:05 PM, 5 Snell Library
Office Hours: TuF after class
Course Description
Textbook
Grading
Tentative
Course Schedule
Course Description
This course provides a
graduatelevel introduction to the theory of computation. We
will study models of computation, decidability, space and time
complexity classes, NPcompleteness, 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:

Introduction to Automata Theory, Languages, and Computation,
by
J. Hopcroft, R. Motwani, and J. Ullman, Addison Wesley, 2nd Edition,
2001.

Models of Computation: Exploring the Power of Computing, by
J. Savage,
AddisonWesley, 1998.
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
The midterm and the final will both be takehome exams  dates to be
determined.