CSC280, Spring 2017: Computer Models and Limitations

Instructor: Prof. Lane A. Hemaspaandra.

Grad TA: Ethan Johnson.

Workshop Leaders: Mikayla Konst and Shir Maimon.

UG TAs: David Fink, Maria Janczak, Lia Klein, Dan Rubery, and Hassler Thurston.

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, third edition, 2013. 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" (third) 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 (most current version, V. 1.2.0, of 2017/2/21/507pm).

Slides: Here (version of 2017/3/5/513pm) are the slides up to and including Chapter 5.

Reading Assignments (most often assigned/posted the evening of 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