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).

Other Important Links:

Some of My Favorite Bits of Science Wisdom:

Other Odds and Ends (Mostly Quotations):

Page Maintained by: Lane A. Hemaspaandra