## CSC280/480, Spring 2021: Computer Models and Limitations

Instructor: Prof. Lane A. Hemaspaandra.

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.
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.
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.
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.

• Due [see the text here... technically due 2021/2/10/325PM, but for the reasons mentioned, you may want to read it all, or skim some key parts, earlier than that; assigned 2021/2/8)]: In SIP ("SIP" will be short for our Sipser, 3rd edition, book) read Chapter 0 (Introduction) and Chapter 1.1 (Finite Automata). That is what corresponds with the slides in class today. And, somewhat unusually, since I usually have the reading trail the class/slides, please also read SIP Chapter 1.2 and Chapter 1.3, even though the coverage of those in class has not yet come.

• Due 2021/2/17/325pm (assigned on 2021/2/15): Read SIP section 1.4. This is generally what we covered in class today, so if you were totally comfortable with and understand today's lecture, you probably can read it quickly or just skim it, since you already will (if the "if" part of this sentence holds) understand it. But if some parts of today's lecture were not clear or went by too quickly, you may wish to read this section quite carefully. And almost everyone will likely want to read the proof of the pumping lemma, as in class I merely gave its core insight, rather than going through the entire proof (which is on the slides, and of course is in the textbook). Also, please review the notion of an NFA, so know its tuple definition, and know what each of the tuple's five parts is (most esp. know the type of the transition function); in class on 2/17, you'll be doing a (perhaps challenging) hands-on exercise for which it will be important for you to come in with a comfortable understanding of NFAs.
• Due 2021/3/1/325pm, but actually, reading it sooner by a few days would be a good idea (assigned on 2021/2/24): Read SIP pages 101 through the middle of page 107 (which you should generally know from CSC 173). Read SIP Section 2.3. If you don't remember SIP 2.2 from CSC 173 (where it typically is outright assigned as a reading---not even from Aho-Ull but directly from SIP in fact), then read SIP Section 2.2 (which covers what a PDA is and why the set of languages accepted by them are exactly the CFLs). You do NOT need to read SIP Section 2.4. But please do carefully review our slides on SIP Chapter 2, and you'll likely want to review especially carefully the proof that the "a+b=c"-inspired set is not a CFL.
• Due in part 2021/3/10/1159PM, and in part the morning of March 17th (assigned on 2021/3/9) Read Part 1 of Midterm 1's instructions (they are linked to from later on this same page, in the "Other Important Links" section). Read them now (March 9 or 10) and then (so that you catch any updates, and so it is fresh in your mind while you are taking the exam), read them again either the evening before Midterm 1 or the morning of Midterm 1 (i.e., the morning of March 17th).
• Due 2021/3/22/325pm (assigned on 2021/3/15): Read SIP Chapter 3 and Chapter 4.1. (Note: This same reading---in fact indeed also from SIP---is typically assigned in CSC 173 by George, so with luck most or all of this reading will be familiar to you.)
• Due 2021/3/24/325pm (assigned on 2021/3/22 and 2021/3/23): Read SIP Chapter 4.2 (this is what we covered in class today). Also read SIP Chapter 5.1 (this is what we'll cover in class on 3/24; so if you don't completely follow the reading that is ok, as we'll cover it in class on Wednesday and that should help, plus after that class you can re-read it if after the reading and class it is not completely clear; TWIST: If you have Thursday recitation, or if you have a Wednesday recitation that is late enough that you'll have time to read Chapter 5.1 between our 3/24 class and your recitation, it is fine to, if you wish, defer the reading of Chapter 5.1 to between our 3/24 class and your scheduled recitation of this week).

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)

• Due 2021/3/31/325pm except if due to the study break you want to do it instead by 4/1/325pm that is ok (assigned on 2021/3/29): Read SIP Chapter Chapter 5.3 except you can skip reading Example 5.25 except do note (as is hidden in Example 5.25's pointer to Exercise 5.6) that $$\leq_m$$ is transitive, namely, if $$A\leq_m B$$ (say via f) and $$B \leq_m C$$ (say via g), then $$A \leq_m C$$ via the reduction $$\rm h(x) = g(f(x))$$ (see the proof on page 242 of SIP for more details).

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.

• Due 2021/4/14/325pm (assigned on 2021/4/12): In SIP read (a) from the start of section 7.2 through 3/5 of the way down page 286 (though and including the words "practical utility"), and (b) sections 7.3, 7.4, and from the start of 7.5 through and including the end of page 313 (WARNING: SIP in Def. 7.18 gives as the definition of NP something that is typically taken as a characterization of NP that follows from the standard definition, and in he as Theorem 7.20 turns what is typically the definition of NP into something that is framed as a characterization of NP; in this course, though, we will take, as our definition of NP, the standard one, namely, the class of languages accepted by nondeterministic polynomial-time Turing machines) (NOTE: in section 7.4 you'll read the proof of the Cook-Levin Theorem, Theorem 7.37; it is hard and it is worth having reading, but I won't be testing you, on Midterm 2, on the details of the proof of that particular theorem, though of course the theorem itself you should know).
• Due 2021/4/21/1159pm. (Assigned 2021/4/20/1216pm.) Read the Midterm 2 Scope page that is linked to from the Other Important Links area below.
• Due in part 2021/4/26/325PM, and in part the morning of April 28th (assigned on 2021/4/25) Read Part 1 of Midterm 2's instructions (they are linked to from later on this same page, in the "Other Important Links" section). Read them now (April 25 or 26) and then (so that you catch any updates, and so it is fresh in your mind while you are taking the exam), read them again either the evening before Midterm 2 or the morning of Midterm 2 (i.e., the morning of April 28th)

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)):

• Due 2021/2/22/325pm (assigned 2021/2/19): This is a home exercise. As with all such, it won't be collected or graded.

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

• Due 2021/3/1/325pm, but this may take you a while, and working on it will likely really help you understand this type of construction, so please start it a few days before that... working on it joint with others is totally fine, by the way (assigned on 2021/2/24): Show that for each regular set L, the language MiddleThird(L) is regular. MiddleThird(L) is defined as $$\{ x ~ \mid ~ (\exists w) (\exists y) [ |w| = |x| = |y| \land wxy \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 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!

• Due 2021/3/8/325pm.
1. (Note: assigned 2021/2/25 but you won't be able to *do* this until the videos in question are posted, which I expect will happen on 2021/3/5): In brief, view one or both (we will try to make two, to offer you more examples, since the two taping TAs will try to use different examples) of the posted videos that will be made on 3/4, and that are covering various problems/skills/exercises/etc. For a more detailed coverage of what to do (and the special case that might apply if you are completely confident that you are on top of everything we have covered so far), please read the paragraph that comprises lines 5-21 of page 15 of our syllabus (V. 1.3.2).
2. (Assigned 2021/3/1.) Prove that if $$L\subseteq \Sigma^*$$ is a regular set and $$B\subseteq \Sigma^*$$, then $$L_{yxy} = \{x\in\Sigma^*~\mid~(\exists y \in B)[yxy\in L]\}$$ is a regular set. In doing this, you may find you will use aspects of the "xy" case we covered today (3/1) in class, but unlike that, might need to use a richer state space (as we often have been doing in tackling a different type of challenge, namely, fractional-language problems). If you find the yxy case easy, then make your own string of x's and y's, e.g. xxxyxyyyyxyyxyxxyxyxy (or perhaps something a bit shorter, e.g., xxyx), and see if you can prove the same result for that case (it does hold).
3. (Assigned 2021/3/5.) Read the "Midterm 1 Scope Page" that is linked to from the Other Important Links area below.
• Due 2021/4/7/325pm. Do as take-home exercises about enumerations/presentations the two pages of "challenge" problems from section 3.2's end (esp. the first question on the first page, and both questions on the second page).
• Due 2021/4/19/325pm. (Assigned 2021/4/16.) Prove that SAT polynomial-time many-one reduces to the set {f | boolean formula f has at least two satisfying assignments}.
• Due 2021/4/21/325pm. (Assigned 2021/4/19.) Prove that if SAT is P-selective then P=NP (equivalent, prove that if SAT is P-selective then SAT $$\in$$ P). (This is Challenge 1 from our current slide set.)
• Due 2021/4/26/325pm. (Assigned 2021/4/21.) Try to prove that if there exists a sparse set S such that $$\overline{SAT} \leq_m^p S$$ (equivalently, there is a coNP-hard sparse set), then SAT is in P (equivalently, P=NP). That is, try to prove Challenge 3 from our slide set (start with the proof used to solve Challenge 2, but you'll need an ADDITIONAL insight!). Even if you don't solve it, trying it will be valuable and will make the solution clearer to you when we go over it on Monday.

Some of My Favorite Bits of Science Wisdom:

• After solving a challenging problem, I solve it again from scratch, retracing only the *insight* of the earlier solution. I repeat this until the solution is as clear and direct as I can hope for. Then I look for a general rule for attacking similar problems, that *would* have led me to approach the given problem in the most efficient way the first time. -- Robert Floyd
• In computer science, elegance is not a dispensable luxury, but a matter of life and death. -- Edsger Dijkstra
• Imagination is more important than knowledge. -- Albert Einstein
• They are ill discoverers that think there is no land, when they can see nothing but sea. -- Francis Bacon

Other Odds and Ends (Mostly Quotations):

• I don't believe it. Prove it, and I still won't believe it. --Life, the Universe and Everything
• It was mentioned on CNN that the new prime number discovered recently is four times bigger then the previous record.
• Sooner or later society will realize that certain kinds of hard work are in fact admirable even though they are more fun than just about anything else. -- Donald E. Knuth
• Getting tenure doesn't really change anything. However, not getting tenure changes everything.
• My late friend Stan Ulam used to remark that his life was sharply divided into two halves. In the first half, he was always the youngest person in the group; in the second half, he was always the oldest. There was no transitional period. -- Gian-Carlo Rota, "Indiscrete Thoughts"
• Fools ignore complexity. Pragmatists suffer it. Some can avoid it. Geniuses remove it. -- Alan Perlis, Epigrams in Programming
• More Quotes from Dijkstra:
* None of the programs in this monograph, needless to say, has been tested on a machine. (From "A Discipline of Programming.")
* Computer science is not about computers, any more than astronomy is about telescopes.
* The question of whether computers can think is just like the question of whether submarines can swim.
• "Supposing a tree fell down, Pooh, and we were underneath it?" [said Piglet.]
"Supposing it didn't," said Pooh after careful thought.

Page Maintained by: Lane A. Hemaspaandra