Computer Models and Limitations

Computer Science 280
University of Rochester
Spring 2015

Instructor: Muthu Venkitasubramaniam

Time: TR 15:25-16:40
Place: Morey 321
Course Web page:

Graduate Teaching Assistant:

Undergraduate Teaching Assistants:

Workshop Leaders:


The required text for the course is Introduction to the Theory of Computation (2ed.) by Michael Sipser. (Please note that this is the second edition)

You may find the following books to be useful references. Note, however, that we will not always be following the same notations as these books.

Topics Outline





CS 173 and MTH150

Course Administration

All homeworks and grades will be posted on blackboard. Course announcement, discussions and notes will be posted through Piazza.


There will be Quizzes every class, Homeworks every week, and 3 Mid-terms. The grade will be based on all tests and workshop participation

Quizzes 25%

Homeworks 25%

Mid-Terms (10+10+10)%

Workshops 20%

Homework Policy

You are free to collaborate with other students on the homework, but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to me. Typed problem sets are strongly preferred.