Instructor: Lane A. Hemaspaandra.
Grad TA: Joseph ("Joe") Saber.
Course Announcements/Library Reserves/Syllabus/Grades/Etc.: Announcements (if any) mostly via Blackboard but also there may be Notes on this page in the Day-to-Day list. Reserves via the library (a few dozen books/etc. are on the list I submitted to the library); our BB site will (as soon as the library creates the link) link to the library's list of those (and how to find them on the shelves or, in some cases, as an online resource). Except for the items on this page (most especially the day-by-day log), most of the course (such as the course-information-document/syllabus, the grades, videos of class sessions via Panopto, etc.) resides in Blackboard.
Prerequisite: CSC 280/480.
Navigation Information:
In your group, you will master one chapter (the one that is matched above with your group) of the Hem-Ogi textbook and prepare slides for and present in class your talks/slides on that chapter for one and a half class sessions, namely, the one and a half class sessions matched above with your group. You do not have to cover the entire chapter (and in fact, doing so might be impossibly much). Rather, each group should choose for itself the "right" amount of material from the chapter so that you fully fill your number of lectures, and cover clearly the part of the chapter's material that you choose to cover (for example, for Chapter 2, perhaps Chapters 2.1 and 2.2 (I don't expect you to more than that, but if you when planning it happen find you have time to cover even more, maybe you might go over the key result, though not its proof, of 2.3); and for Chapter 3, my guess is your natural coverage likely would be Chapters 3.1 and 3.2 (I don't expect you to more than that, but if you when planning it happen find you have time to cover even more, maybe you might present what the RESULT of 3.3 is, though not its proof); and for Chapter 5, well, probably Chapters 5.1 (it has no result but is key groundwork) and 5.2, and possibly, depending on how time guess none or some part of 5.3).
You will be graded on the quality of your entire unit (and that grade will be shaped in part by and whether you send in on time and done-well the required web-page blocks and do any other of the providing-of-material logistics, but mostly by the quality of the slides and the quality of the presentations, though those two items won't get separate grades from each other; rather, you'll a bit after the end of your project get your overall project grade). In particular, some time after your final talk, after, if Joe heard your talks and is available, he and I have had time to talk with each other, so perhaps that evening or a day or two later, via Zoom you'll (it can be your whole group, or you can send a subset, who can convey the grade and the feedback to the rest of the group) meet with me (and perhaps also Joe)---we all should set up the appointment ahead of time---for our feedback and to get your grade.
Please, when preparing your slides/talks, note that there is an errata for the book, which can be reached via Errata link on this page. Please do look at it so that you are aware of that errata's collection of corrections to the book's text.
The details on how/what you'll hand in and do are as follows (be careful... this is a bit complex):
Please start right away, because digesting a chapter, making excellent slides, and presenting them in a clear, charismatic way to the class is a serious, long, hard task. (And the talks start relatively soon, esp. for the group presenting Chapter 3 as that goes first; note: the order in which the chapters are scheduled took into account the degree of challenge of the chapter's material; that is why Chapter 3 is coming before Chapter 2)
BEWARE: On 2/28, a few days after this paragraph was first posted, modified its requirements. The change is will email us your draft-slides just once (by noon on the day of your first talk), but that will have the draft of both day's slides (and probably the version you'll use for the first day will be a lot more than a draft, since you'll be just 2 hours away from giving it). The various other requirements (e.g., your revised final slides being turned in, and paper copies in a certain format at each class for me and the TA) are unchanged. And here is the thus-revised text of the paragraph (the only sentence that changed is the first sentence): You must also, no later than noon on the day of your first talk, email to csc286staff "at" lists.rochester.edu your entire set of slides (for BOTH talks; caveat: it however is ok if between the two classes you modify the slides for the second day) as a *pdf file*, cc'ed to every member of your group. Then, no later than 1159PM of your *final* day of talks (that time frame is so that you have by then have incorporated any needed fixes/corrections that were mentioned to you during the talk), you should in a single email mail csc286staff, cc'ed to every member of your group, as a single PDF file your entire set of PDF files for the chapter, AND your source code (either as PowerPoint if you used PowerPoint, or if you used latex as a zip archive with ALL the source files/pictures/etc.); note that each group's 1.5 days of talks should look uniform within the group, e.g., you cannot have 1 of your talk days be latex-based but the other be PowerPoint based; rather, all of it should look like a unified whole from a single overall PowerPoint or latex source---but of course different subparts of the group may have made different parts of the slides---the \input and \include commands are helpful for that in latex. Also, your first slide should clearly and explicitly list the names of all your group's members, and your Vorlon-or-Minbari-or-Narn nature, and of course what chapter you are covering. (Note: The book has an online transparencies page (it is not cheating to look at the slides there; it is cheating to plagiarize from them; it might be wise to simply not look at them until you have drafted your slides, or ever, so that you draft your own slides in your own group's voice).) Also, at the start of class on the days of each of your talks, you need to give to the TA and me your slides for the class, printed 1-up (but you may print the page 2-sided), and with page numbers, and stapled. (We likely will use those hardcopies to make notes to ourselves during your talks.)
Also, by no later than 6PM on each of the two classes at which you speak, please (i.e., you must) email to csc286staff "at" lists.rochester.edu a suggested "web page block" for (your part of) that day, including a suggested brief title (e.g., "Chapter 3 (P-selectivity and Tournaments), Day 1") and then a text (but HTML-safe, so do not put in a greater than or a less than sign as those blow up html unless one is tricky) blurb that describes what you covered, e.g., a text block similar to what I have for each day of the course on this web page, e.g., day one of the Chapter 3 group (Vorlons) perhaps might be: "Reviewed tournaments and the existence in tournaments of log-small superloser sets; P-selective sets; left cuts of real numbers; the fact that the left cut of any real number in (0,1), even an undecidable one, is P-selective, and the fact that follows from that that there are undecidable P-selective sets... so P-selective sets are, information-wise, polynomially close (per length, so to speak) to P, yet can be undecidable (or in fact even beyond the entire Kleene Hierarchy)... P-sel functions differently regarding different measures of hardness!; P/poly (small circuits); mentioned P^{SPARSE} = P/poly; P-sel \subseteq P/poly... and even P-sel \subseteq P/quadratic; P-sel \subseteq PP/linear." Caveat: As to what I will post on the web page, I might edit what you send---or write a summary myself instead.)
As to the talks, you have the entire 75-minute class session of the full-class you are assigned and 1/2 the 75-minute class session in the half-class session you are assigned; but you should if possible try to leave at least a few minutes free at the end of each for questions, which you of course should answer expertly based on your (by then) strong familiarity with the chapter you are presenting. I am not going to, this year, make a rule that says everyone in the group has to present at least some of one of the slides during presentation; some groups in the past have done that (though it can get a bit rapid-tag-team-like as to hand-offs between speakers), but this year I am going to leave the division of focus up to you, e.g., one person might do a lot on creating the slides and might not present anything, and another who loves presenting things well might do a bit less on creating the slides but might do a substantial amount of the presenting. More generally, please work carefully with your groupmates on preparing the talk, so you ALL are involved in and aware of the whole process, and are helping each other in mastering the material of the chapter you have been assigned. In preparing the talk/slides, you may use any inanimate resource (books, papers, the internet, etc., except you should not seek help from ChatGPT or similar things in writing or even in proofreading your slides), but may not actively seek help from any human---not even me---other than your groupmates (not even by posting on the web or by email asking anyone other than your groupmate questions or requests for help); your group is on point on the task of doing on its own this big task.
Everyone in the group gets the same grade, except if a person skips the entire project (doesn't show up to any meetings or do any work), that person would get a 0 (if those who did show up let me know of that and if the person indeed outright didn't show up at all); obviously, don't let that happen... but beyond that, please pull your fair share of the weight, of course, not just because I'm asking but also in fairness to your groupmates (and to ensure that you yourself get your share of the experience/learning of mastering/preparing/presenting a body of material).
Finally, I will allow a small but important exception to the immediately preceding paragraph's prohibition on help from anyone outside the group. However, as I write this (on March 19th), there currently is the possibility of a strike involving graduate TAs at UR, and if that happens, of course any TA who is part of the strike would not be available for any TAing activities (in which case any of the following that would occur during affected days would not apply). But if a grad TA of the course is available, you may by mutual agreement with the grad TA do a single run-through of your talk (in which you'd present your 1.5 days of slides, and the TA would either during or by chatting with your *immediately* after you presented your sides give you the TA's constructive feedback on the slides and the presentation). Such a run-through is not required, and the feedback is "free" and intended to be constructive: you will not be graded on your run-through... the feedback you get if you do one is purely intended to help you, if you wish, revise your slides and presentation if you feel that following some or all of the TA's comments will improve them. If you will be doing a run-through, please arrange the date/time (and location for it: either Zoom or some physical location) with the grad TA long in advance (but again, keep in mind that if a grad TA is on strike during the planned date, then the run-through will not occur).
Note Added 2025/4/5:You will get your Term Project grade
(and any feedback) at a zoom session in the early evening, one
day after your group's final talk. Your group must send at
least one person to be at that zoom session (though as many of
your group came come as you like; but make sure, those of you who
attend, to convey the feedback and grade to your
groupmates---more on that below!). I will be at that zoom of
course (and it is possible that Joe might also
be at that feedback session). Beware: If you arrive early,
you will find yourself in the waiting room, as right up to
the start time mentioned below
the TA and I may be discussing the feedback and the grade, so don't
worry if you find yourself initially in a waiting room.
The meeting dates/times, and once you send
the info in which one person in the group has committed to
definitely attend the meeting and to let all group members who
could not attend the meeting know the grade and feedback, are
the following (and the URLs for each are NOT on this public web
page but are sent to the whole class via a BB Announcement
posted on 2025/4/5):
(be careful... the times and URLs on 4/8 and 4/17 are the same as
each other, but the meeting on 4/10 is at a different time and
a different URL!):
Vorlons = April 8, 615PM
(person who committed to definitely attending: Kevin/Zahra).
Minbari = April 10, 645PM (person who committed to definitely attending: Shikhar).
Narn = April 17, 615PM(person who committed to definitely attending: Isabel).
Please, as per the April 5 BB announcement/request on this:
Each group should no later than noon on April 7
send email to our standard course address,
csc286staff@lists.rochester.edu, letting us know at least one person who has committed to attending that Zoom (more or all of the group's people of
course are welcome to come, but this is about one who has
committed to definitely coming so we know someone will be there
to get the grade and feedback!),
and that person should make sure to attend and to share with all in the
group who did not attend the project grade and any feedback. And, to help the group all know who that person is,
please, whoever sends the email letting us know who that person is, make sure to carbon-copy your email to all of your
groupmates, and I'll also add that person's name above in the lines
with the meeting times.
Author = {U. Sch{\"{o}}ning}, Title = "A Low and a High Hierarchy within {N}{P}", Journal = "Journal of Computer and System Sciences", Year = "1983", Volume = "27", Number = {1}, Pages = "14--28",give or take the fact that that paper is in the quirky model of keeping the empty set and Sigma^star off the table (a quirk that was soon abandoned)---the quirk is why Schoening uses \(NP^-\) rather than \(NP\).
Oh... this is not a reading assignment, but in case you want a reference for the brief comments on lower bounds (the issue Sam mentioned when asked what glaring hole existed if one just was proving better and better upper bounds), the paper that introduced lower bounds on lowness (and also on so-called extended lowness, where one can get absolute lower bound results), was (from so long ago that even my name was different) "1992, 39, JACM, Eric Allender and Lane A. Hemachandra, Lower Bounds for the Low Hierarchy," which the UR library will also give you direct access to since it gives online access to most key CS journals.
Useful Links/Info:
Some of My Favorite Bits of Science Wisdom:
Other Odds and Ends (Mostly Quotations):