CSC280, Spring 2014: Computer Models and Limitations

Instructor: Prof. Lane A. Hemaspaandra

TAs: Dan Hassin, Mark Mullock, and Xing Yan.

Workshop Leaders: Julian Lunger and Samantha Piccone.

The Course Catalog Description: (The school is in the process of updating this course's description in the course catalog; the blurb below is a more up-to-date one than the one in the course catalog.) This course studies fundamental computer models and their computational limitations. Finite-state machines and pumping lemmas, the context-free languages, Turing machines, decidable and Turing-recognizable languages, undecidability.

Textbook: Introduction to the Theory of Computation, Michael Sipser, (the rather new) third edition, 2012. Be careful not to accidentally get the first or second edition. Note that we will be using the (standard, USA-version) third edition, not the "international" edition; in the international edition apparently some problem numbering differs, so if you use the international third edition (which you might get if you buy a used one, so be careful), you may do the wrong problems (and so will end up with 0's as you'll have done the wrong problems). (And no, I don't work for the publisher; all my books are published by Springer.) The ISBN of the US edition (the international edition has slightly different ISBNs) is listed by the publisher as: ISBN-10: 113318779X and ISBN-13: 9781133187790. On the other hand, the right book is also on reserve in the library, though you will be using it very, very often (you may find it comforting to sleep with it under your pillow!).

Prerequisites (very important): CSC173 and MTH 150.

Course Information Document/Syllabus: syllabus (version, V. 1.3.2, last updated 2014/3/26).

Other Important Links:

Some of My Favorite Bits of Science Wisdom:

Other Odds and Ends (Mostly Quotations):


Page Maintained by: Lane A. Hemaspaandra