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.2, of 2017/4/4/1020pm).

Slides: Here (revision of 2017/4/2/702pm) are the slides up to and including Chapter 5. The slide set for the 2017/2/27 lecture on Lewis Carroll's election system and the class of sets computable by parallel access to NP is available here; the paper that talk is about (this literature pointer is just in case you want to know where the full version can be found; this is not a reading assignment, i.e., you are *not* required to go read that paper) is: "Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System is Complete for Parallel Access to NP," E. Hemaspaandra, L. Hemaspaandra, and J. Rothe, Journal of the ACM, V. 44, Issue 6, pp. 806-825, November 1997; UR students can get to that paper free online through the UR library's ejournals gateway. Here is the slide set (consisting of slides 61 through 86 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.

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