CSC280/480, Spring 2021: Computer Models and Limitations

Instructor: Prof. Lane A. Hemaspaandra.

Grad TA: Michael Chavrimootoo.

Workshop (though called Recitations in CDCS) Leaders: Elias Neuman-Donihue, Hecong Wang,and Timothy Hornick.

Office Hour/Class TAs: Kalen Frieberg, Mandar Juvekar, Patrick Phillips.

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, 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.3.4).

List of Our Coming MainClass/Workshop/OfficeHours(both OOHs and ROHs) 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 nine workshops (which are called "recitations" in registrar terminology).

ROH Assignments (who is in which) and Weekly ROH/nonROH Settings: ROH Assignments: These will be signed up for by you online during each ROH week. Which weeks are ROH weeks: Whether a week will be an ROH week will be posted shortly before the given week, as ROH/nonROH-ness is dynamically decided based on pace/flow and other factors.

Week 1 (Feb. 1-5): nonROH.

Week 2 (Feb. 8-12): ROH.

Week 3 (Feb. 15-19): ROH.

Week 4 (Feb. 22-26): nonROH.

Week 5 (March 1-5): ROH.

Week 6 (March 8-12): nonROH.

Week 7 (March 15-19):
Complex, special-case week.
Wednesday, 3/17, 325PM Eastern DAYLIGHT Time is Midterm 1; please make sure to start it at 325PM sharp!
There will be no ROH attendance grade for this week.
Students will not sign up for a ROH.
All ROHs and OOH/ROHs of this week that occur before 325PM on Wednesday will exist but will function as OOHS (open office hours); please use them if you need help in preparing!!!!
And all ROHs and OOH/ROHs of this week that occur after 325PM on Wednesday 3/17 are canceled.
There will be no WSs this week and no WS attendance grade this week.
You should at 325PM NOT come to our class Zoom, which in fact won't exist. Rather, you should on 3/17 at 325PM sharp, Eastern DAYLIGHT Time, take Midterm 1, via BB; you will at 325PM be able to find it in our BB area, inside BB Parts of Course Content, and within that within a folder called Midterm 1.

Week 8 (March 22-26): ROH.

Week 9 (March 29-April 2): Special case: ROH, except 3/30 is a study break day and so there are no office hours or ROHs that day. Thus the days for ROHs are 3/29, 3/31, 4/1, 4/2; and (since that decreases by about 1/5 the number of ROH half hours) you MAY freely sign up in the "4th" slot for an ROH. The sign-up sheet for the ROH's will go up later than usual (likely some time on 3/28), and will lock later than usual (namely, 315PM on 3/29).

Week 10 (April 5-9): ROH.

Week 11 (April 12-16): ROH.

Week 12 (April 19-23): nonROH.

Week 13 (April 26-30):
Complex, special-case week.
Wednesday, 4/28, 325PM Eastern DAYLIGHT Time is Midterm 2; please make sure to start it at 325PM sharp!
There will be no ROH attendance grade for this week.
Students will not sign up for a ROH.
All ROHs and OOH/ROHs of this week that occur before 325PM on Wednesday will exist but will function as OOHS (open office hours); please use them if you need help in preparing!!!!
And all ROHs and OOH/ROHs of this week that occur after 325PM on Wednesday 4/28 are canceled.
There will (due to Midterm 2 grading) be no WSs this week, but there was a WS attendance grade this week, based on viewing prerecorded video (namely, NFA Equivalence via QBFs, by my postdoc David Narvaez). (More details on that were sent by BB announce on 4/26.)
You should at 325PM NOT come to our class Zoom, which in fact won't exist. Rather, you should on 4/28 at 325PM sharp, Eastern DAYLIGHT Time, take Midterm 2, via BB; you will at 325PM be able to find it in our BB area, inside BB Parts of Course Content, and within that within a folder called Midterm 2.

Week 14 (May 3-7):
Complex, special-case week (a nonROH week but WSs will not be via Zoom on Wed. and Thur. but rather you'll need to on Saturday May 1--Monday May 3, or early enough on Tuesday May 4, do a certain video-watching and then send a certain email with a good answer to a question I've posed regarding the video's material).
As to ROHs, it will be a standard nonROH week: the ROH TAs will be in the Zoom classroom both days to rotate between breakout rooms, and as usual in nonROH weeks, they will have their pure OOH/ROH office hours (but not their ROH office hours). So as usual in nonROH weeks, there will be no ROH attendance grade for this week and students will not sign up for an ROH.
Michael and I will of course have our usual office hours this week.
However, regarding WSs, this is a special-case week. There will be no in-person-via-Zoom WSs this week, but there WILL be a WS attendance grade this week, based on viewing a recorded video (a 52-minute video of a talk I gave in Theory Canal in April, about Online Bribery---it is about complexity but with that being used in the setting of computational social choice, and in particular, regarding attacks on elections; you can find it by 2PM on May 1 in our CSC 280/480 Workshop Recordings folder under the rather long name 2021-05-05-WorkshopSubstitute-DUE-BY-2021-05-04-530PM-EDT-Online-Bribery-Theory-Canal-Lane-Hemaspaandra-20210414-1220), and then sending a certain email that will show us, via an answer that you'll include in that email to a certain question I'll pose, that you watched the video; we need to *receive* that email no later than 530PM EDT on TUESDAY MAY 4 (and we need for your answer within the email to make convincingly clear to us that you watched the video). EXTREMELY IMPORTANT: NOTE THE TIME FRAME: This is DUE well *before* the May 5 and May 6 WSs that it is a substitute for. Please make sure to complete this either now or at least before the deadline, since we will NOT be giving credit for late credit requests that we received after the strict 530PM deadline; note that the deadline regards when your email is *received*, so do make sure to send you email safely long before the deadline, and of course don't slam shut your laptop so lightning-fast after hitting send that the email doesn't even get out until you next open your laptop---you'd end up getting a 0% on this attendance grade. The full details on this WS attendance grade, which is done via the viewing and the email, will be sent to you via BB Announcement some time between 1230PM and 2 EDT on Saturday, May 1; please do read that BB Announcement carefully, and then act on it in time to get the 100% attendance credit!
Regarding that WS attendance grade, we'll have all its grades posted in BB no later than 1159PM EDT on Tuesday, May 4, and if you did send an email in time but got a 0% (and you think your answer was such that it would have made convincingly clear to us that you had watched the video), then you have only until 1159PM EDT Wednesday, May 5 to ask us to check into whether you were incorrectly not given credit; no requests for such checking will be accepted after 1159PM EDT Wednesday May 5.
As you know, the course has no final exam.
We will have class on both Monday and Wednesday of this week, and those are the final two class sessions of the term. As per the syllabus, there will be no appealing attendance grades for those two classes; rather, I will (unless for forget to take attendance at the given class) right at class either read through the list of all names so you can say "here," or (far more likely) we'll use Qwickly as usual but immediately after the Qwickly attendance is taken I'll read through the names that Qwickly claims is NOT attending, so that if I read your name and you ARE attending (but perhaps you could not connect to Qwickly for example), you can say right then and there at the Zoom session "I AM HERE!" and I'll right at that moment override the attendance cell for you for that day and mark you as being here.

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