CSC280/480, Spring 2023: Computer Models and Limitations

Instructor: Prof. Lane A. Hemaspaandra.

Grad TAs: Hanjia (Bruce) Lyu and Hecong (Alan) Wang.

Workshop (though called Recitations in CDCS) Leaders: Ethan Ferland, Ian Harding, and Henry Welles.

Office Hour/Class TAs: Vuong Ho, Zihao (Ziggy) Lin, and Quan Luu.

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, and NP-completeness.

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 no, I don't work for the publisher!) 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. You will be using the book very, very often (you may find it comforting to sleep with it---or your Kindle or whatever if you get it in eTextbook form---under your pillow!---warning: don't actually sleep with your Kindle under your pillow).

Prerequisites (very important and required): CSC173 and MTH 150.

Course Information Document/Syllabus: course information document/syllabus (most current version, V. 1.1.2).

List of Our Coming Items (including all ROHs and also those OOHs that are OOH/ROHs or that are Zoom-based pure OOHs) If They Will Be Reached Via Zoom Meeting Links/Passwords: Available via a link in our Blackboard area, via, within "BB Parts of Course Content," the link "Zoom Meeting Manager: Your springboard to all our Zoom meetings."

Slides: The main slide-set is available in the "BB Parts of Course Content" part of our Blackboard area.

Workshop Assignments (who is in which): These were set by you as you registered via the registrar's system; each of you must be registered for exactly one of the eight workshops (which are called "recitations" in registrar terminology).

ROH Assignments (who is in which): The ROH assignments can be found inside our BB area, via an item/link within our folder BB Parts of Course Content.

Which Weeks Are ROH Weeks: Whether a week will be an ROH week will be posted here (sometimes very) shortly before the given week, as ROH/nonROH-ness is dynamically decided based on pace/flow and other factors.

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

Exercises/Problems in cases when you are expected to work on them before the workshop or ROHs (or class sessions) at which you'll be going over their solutions (all exercise and problem numbers are from SIP unless otherwise stated) (note: for some or many workshops (resp., ROHs), all the problems will be given and worked on at the workshops (resp., ROHs), but THIS listing is cases where you need to, before the workshop (resp., ROHs), do some exercises or so on---which often some WS members will then be asked to put up the answers to (resp., some ROH members will be asked to present the answers to)):

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