CS 280 Instructor Page

Course Name: Computer Models and Limitations

Instructor: Prof. Lane A. Hemaspaandra

Graduate TA: Scott Ames

The Course Catalog Description: This course studies fundamental computer models and their computational limitations. Finite-state machines and pumping lemmas, the Chomsky hierarchy, Turing machines and algorithmic universality, noncomputability and undecidability, tradeoffs between power and formal tractability.

Textbook: Introduction to the Theory of Computation, Michael Sipser, (the brand new) third edition, 2012. Be careful not to accidentally get the first or second edition.

Prerequisites (very important): CSC162 OR CSC172 OR MTH172.

Course Information Document/Syllabus: Here (version 1.15, last updated 2013/4/1/8:36PM).

Slides: Here (version of 2013/4/12/3:52PM) are the slides up to and including Chapter 5, and here is the slide set (consisting of slides 67 through 87 of the slide set for CSC 286/486, a course all UR CS Ph.D.-program students are required to take!) that we'll use for our introduction to P and NP. In the dream case, we'll manage to cover all these slides... and, if there is time left after that, then for additional lectures (probably on applying P and NP to elections) we'll have stand-alone lectures, most with their own slide sets. The slide set for the 2013/4/24 lecture on Lewis Carroll's election system and the class of sets computable by parallel access to NP is available here. The slide set for the 2013/5/1 lecture on "Search versus Decision for Election Manipulation Problems" is available here.

Reading Assignments (usually assigned the class before it is due):

Homework Sets (this list does not include the large number of homework-style problems you'll solve in your workshop):

Other Important Links:

Some of My Favorite Bits of Science Wisdom:

Other Odds and Ends (Mostly Quotations):


Page Maintained by: Lane A. Hemaspaandra