CSC280/480, Spring 2023: Midterm 2 Scope

Midterm 2's Scope

The scope of Midterm 2 as to TMs/decidability/undecidability includes all the material we covered in class, readings, exercises, WSs, ROHs, or slides; and of course the questions may be new questions or issues that connect to or draw on any of those things. Note that the 2/20, 2/22, and 2/27 classes, though they happened before Midterm 1, were our start on TMs/computability/etc., and so their material is certainly in scope. (As to the rest of the first half of the course, although the exam is not primarily focused on it---it is not a cumulative final exam but is rather Midterm 2---since the course builds on that material, you of course are expected to know it and it may come in insofar as it is related to material in the second part of the course. For example, it is completely possible that you might be asked about the complexity of the set {<M> | L(M) is a context-free language}.) One special point: To help you have more time available, while studying, and because we did not stress the following quite advanced machinery, I guarantee that we will not have an essay/short answer question that requires you to give a proof that a certain set is not Turing-recognizable or is not co-Turing-recognizable using the methodology employed in the proof that appears on slides 9 and 10 of our "Chapter 5, Parts 2/3" main slide set; my saying that does not mean that you are not expected to know that methodology (for example, if you are asked to classify a set as to where it falls as to its (or its lack of) decidability, Turing-recognizability, and/or co-Turing-recognizability, that methodology is one approach you might employ, or might run in your head; but what I am saying is that I guarantee that we will not require you to write out a proof using that method as part of your handed-in-exam-material).

As to our P/NP/NP-completeness unit, the scope of what might be asked about it on Midterm 2 is the material on that unit covered in class, readings, exercises, WSs, ROHs, or slides; class, readings, WSs, ROHs (and of course there certainly might very well be on Midterm 2 questions/issues that are not on those slides but that connect to or draw on the slides' material). The slides we showed regarding that unit are the 24-slide main set, all of which were covered and are in scope, and then in the middle of the 4/5 class we started the "Power of Self-Reducibility" slide set, and regarding that self-reducibility stream of coverage, in scope on the exam is all that we covered in class/slides/reading on that EXCEPT Challenge Problems 3 and 4 are not in scope (as we likely will not cover Challenge Problem 4, but even if we do, it will not be in scope on Midterm 2; we will cover Challenge Problem 3, but it will not be in scope on Midterm 2; however the similar but easier Challenge Problem 2 will be in scope, as will also be Challenge Problem 1). Note that you can find writeups of solutions to Challenge Problems 1 and 2 (and in case you are interested, also Challenge Problems 3 and 4) in the arxiv report linked to from the reading that was assigned on 2023/4/10; I urge you to read in that the notions, problem statements, and solutions corresponding with Challenge Problems 1 and 2 and the things those employ, so certainly including the appendices of https://arxiv.org/pdf/1902.08299.pdf that solves those, and also reading in that arXiv report the related problem/notions/definitions.

When I say above something like "class, readings, exercises, WSs, ROHs, or slides," do keep in mind that things that are in at least one part of the union are in scope, even if there are other parts of the disjunction that they are not part of. And, beyond that, it is completely possible that things will be on the exam that are in the covered domains broadly construed (computability and NP/complexity) that you have not seen before, but rather that require you to, perhaps in creative, new ways, display the skills you've acquired in those domains (and so are things that in some narrow sense don't even fall within the above disjunction).

Additional Comments

Midterm 2 will be April 19, 2023, 325PM-440PM. Midterm 2 counts for about 1/3 of your course grade. Do not miss it. (Even if the day before you for example are so closely exposed to COVID that you go to UHS and they instruct you not to come to classes, contact us immediately via email to csc280gradta "at" cs.rochester.edu so we can arrange for you to take it at 325PM on 4/19, with your laptop's/phone's camera on you for Zoom-proctoring and with a TA doing the proctoring.)

The "Midterm 2's Scope" section above defines Midterm 2's scope, and I likely will refer all questions on the scope to that above section, as it was written carefully. Nothing below alters the above specification of Midterm 2's Scope.

However, let me mention as a comment that, although you of course should know the entire set of things that are in scope, one facet of studying that often is extremely important is to review and thoroughly understand every exercise/problem that you have seen in class, or at workshops, or at ROHs, or on the slides, or that is a worked exercise in the "body" reading of the covered parts of Sipser. By thoroughly understand, I don't mean "have the problem and solution memorized without understanding why the solution solves the problem," but rather I mean that you should understand the flavor of the solution so well that you can use the idea/approach/technique in other settings, and even vary and adjust it as needed, or synthesize it with other things, as needed to solve new challenges on questions that fall within the general domain of the topics we have covered. (Although it is not impossible you will be asked problems you have seen before, it is very possible that you will be asked problems you have not seen before.)

I will not be giving out a "sample midterm" or its solutions. You should study not to echo a sample midterm, which might well incorrectly focus you just on the things that happened to be asked on it, but rather should study to make sure you have a good, broad, flexible command of the material. I also won't answer questions about the format of the exam or the format of its questions; I want you to study the material broadly for the sake of understanding it, not to study to match some comments on format. (However, I mention in passing that the exam (which I have not yet written as I write this so the following is just a guess by me on 4/12/2023) is likely to both have various places where you have to fill in an area left for you to fill in, and is also likely to have places where you have multiple-choice answers... there might even be a few True/False items.

I may post for you a preliminary version of Midterm 2's instructions, before the date of Midterm 2. If so, I will announce it so you can save time on exam day by reading them ahead of time (I did do the same on Midterm 1). If I after that (if I do that) make any nonminor change to the instructions between when I announce that the preliminary version is posted and the exam, I will let you know of that via an announcement through blackboard. As you may see on those instructions, there (in a certain sense) will be no partial credit on Midterm 2. That does not mean that every 20-point question will be such that you get either zero or 20 points. For example, if a stated-as-10-point part of a 20-point question has 4 subparts (perhaps four blanks to fill in, or four multiple choice questions) each stated as worth 2.5 points, then the (only) possible scores on the 10-point part are 0, 2.5, 5, 7.5, and 10. However, if a short answer/fill-this-in subpart was worth some number of points, your answer must be completely correct to get that number of points, and if not you will get zero points, even if you were missing just a single parenthesis. So please check your answers on short answer/fill-this-in parts extremely carefully. (Caveat: The above might not be completely correct. In particular, it is *possible* (but not at all certain) that for a *very* small number of problems or problem parts, such as perhaps a particularly challenging item or two), the problems or parts themselves will state that they are an exception to this, i.e., and that there might be partial credit. Even in that case, to get any partial credit you'd likely need to have the answer basically perfect except for some utterly minor, trivial thing. So that you can easily spot any such problem or item, on the exam I'll put such a declaration into the problem's or part's instructions in boldfaced italics, although I mention to you that other things also may be in boldfaced italics.

Again, the scope of Midterm 2 is as defined in the scope section above on this page, and nothing below alters that. But I mention in passing that the following are a few of the higher-profile or more difficult items, and skills/flavors/areas/problem-flavors, that we have covered:

You definitely want to come into the exam knowing comfortably and well everything just mentioned on this list. (My saying that doesn't change or limit the scope definition at the top of this page. Rather, I'm simply mentioning here that these are some high-profile things that we have covered, and so it is possible that some or all of them might appear in the exam, possibly for quite a few points. But of course, do come in knowing everything that is in scope please.)

Again, the scope of Midterm 2 is as defined in the scope section above on this page, and nothing below alters that. But, big-picture and bottom line: please come in with confident command of the material. Everything listed as being in scope is in scope. And above I also "mention in passing that the following [i.e., the bullet-point list above] are a few of the higher-profile or more difficult items, and skills/flavors/areas/problem-flavors, that we have covered." So I'd urge you to study intensely, using all the tools, such as office hours, attending the many OOHs, attending your WS (and perhaps some extras, perhaps via watching the recordings) on 4/12 and 4/13, reviewing the material and problems we've covered, reviewing the techniques and tools we have covered, reviewing the recordings we've made of lectures and WSs, and working with fellow students to master the material. Coming in very well-prepared would be a very good idea!

I expect the rules regarding what you can and cannot have access to during the exam will be the same as on Midterm 1 (even regarding the self-prepared notes, but also all the constraints on those notes).

Posted 2023/4/12; last modified 2023/4/12/815PM.