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:
This reading is reviewing some basics of discrete math/etc., and then is covering work on finite-automata theory that was covered extremely carefully in CSC 173. If you took CSC 173 very recently, this reading may go relatively quickly and smoothly for you. If you took CSC 173 long ago, your memory of CSC 173 may have faded, and so---although Sipser is a beautifully written, remarkably readable book---the reading will be as quick and smooth as if you did remember it very well, and so to help you best get you back to where you got to in CSC 173 on some of these issues you might want to partner with classmates to go over the material. The ROHs and the WSs this week will go over examples of the two most interesting constructions in that reading: turning NFAs to DFAs (aka the subset construction) and turning DFAs into regular expressions (using GNFAs as a key tool); in concept, you should remember NFAs and regular expressions (since you had them in 173), but if you don't remember them well, please do try to have read in SIP the definitions of NFAs and regular expressions before your ROHs/WSs, and in the dream case, have skimmed the whole reading before your ROHs/WSs (my apologies to those who had ROHs already, although DFAs/NFAs/RegularExpressions are all covered in our 173 prereq so with luck they were not a problem for you).
And, when you do the reading of Chapter 5.1, also read the document I've linked to below via an "Other Important Links" link called: "A likely very useful template (regarding the task: prove a problem undecidable by contradiction): template and a worked example of using the template." It sets up a framework that may make a bit easier the challenge of proving languages undecidable (something you'll be doing even during the 3/24-3/25 recitations, so having seen the template may be helpful)
Re-reminder: If you have not read the "Other Important Links" document "A likely very useful template (regarding the task: prove a problem undecidable by contradiction): template and a worked example of using the template" and the worked example it provides yet, please, please make sure to do so before your ROH and before your WS (that reading was due 3/24); that template/framework is central to our SIP-world approach to proving things undecidable.
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)):
But this is a type of problem that I think people much need more practice on, and this is that. It is important you put time in (either alone or in groups) on this exercise over the weekend, since just seeing me present a solution in class on 2/22 won't improve your skills on this type of problem nearly as much as if you work on the problem yourself this weekend; even if you try but fail to solve it, you'll be far, far more likely to understand the solution I put up than if you did not try to solve it.
We will not be working in groups or individually on this problem in class on Monday; you are expected to have already worked on it over the weekend. And in class, I'll present a solution. (If you feel already completely confident on how to solve this type of problem, and can flawlessly write down a 5-tuple that solves this with the approach that is analogous to what we done in class on 2/17 for first halves of regular sets, then challenge yourself by trying to solve this without any "moving backwards" being used as part of your solution; to achieve that, you may have to change from having your state set be \(\{S\}\cup Q^2\) to instead being \(\{S\}\cup Q^3\).
As always, try to first come up with a big-picture idea for the strategy/approach of your solution. And THEN go about implementing that, via building the appropriate 5-tuple.
(It is not at all unlikely that problem(s)/issue(s) related to this problem could appear, for example, on Midterm 1.)
Here is the problem. Show that for each regular set L, the language FirstFifth(L) is regular. FirstFifth(L) is defined as \(\{ x ~ \mid ~ (\exists y) [ |y| = 4|x| \land xy \in L]\}\).
To solve this, you should note that if L is regular, there is a 5-tuple giving a DFA accepting L. And then you should show how to, in terms of the components of that 5-tuple, define (as a new 5-tuple!) an NFA L' that accepts FirstFifth(L).
To solve this, you should note that if L is regular, there is a 5-tuple giving a DFA accepting L. And then you should show how to, in terms of the components of that 5-tuple, define (as a new 5-tuple!) an NFA L' that accepts MiddleThird(L). You of course will want to first develop a strategy for your proof: how many "fingers" will you use and what will each be doing? But also, by now, you really need to be getting comfortable with moving from a mental model of an NFA to a carefully written and fully correct 5-tuple that defines the NFA. If you're having trouble with this type of problem, or writing 5-tuples, please stop by a 2/25 or 2/26 office hour!
Other Important Links/Info/Resources:
Some of My Favorite Bits of Science Wisdom:
Other Odds and Ends (Mostly Quotations):