CSC280/480, Spring 2018: Computer Models and Limitations

Instructor: Prof. Lane A. Hemaspaandra.

Grad TA: Andrew Read-McFarland.

Workshop (though called Recitations in CDCS) Leaders: Shir Maimon and Brandon Willet.

UG TAs (they also are the Tutorial Leaders): Jackson Abascal, Michaela Houk, Joel Kottas, Andrew Peck, and Colin Pronovost.

Tutorial Times: Here.

The Course Catalog Description: 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 may end up with 20-percent grades on some of the tutorials as you will not have attempted the right 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: course information document/syllabus (most current version, V. 2.2.5, last revised 2018/4/10/1141pm).

Slides: Here (version of 2018/1/14/532pm plus some updates, the most recent done 2018/4/03/1135pm) are the slides up to and including Chapter 5. Here is the slide set (consisting of slides 1 and 61 through 85 of the slide set for CSC 286/486) that we'll use for our introduction to P and NP.

Reading Assignments, starting with the date/time the reading is DUE:

Exercise Sets, starting with the set number and then at which tutorial session you will hand in parts A and B of the given set (all exercise and problem numbers are from SIP unless otherwise stated):

Other Important Links/Info/Resources:

Some of My Favorite Bits of Science Wisdom:

Other Odds and Ends (Mostly Quotations):

Page Maintained by: Lane A. Hemaspaandra