Instructor: Lane A. Hemaspaandra.
Grad TA: Siddharth ("Sid") Vashishtha.
Course Information Document/Syllabus: Version 2.0.0.
Course Announcements/Library Reserves/Etc.: Reserves via Blackboard, Announcements (if any) mostly via Blackboard but also there may be Notes on this page in the Day-to-Day list.
Prerequisite: CSC 280/480.
Please review all the slides we covered in class today (since reviewing what was covered is implicitly a reading/study assignment after each class, I typically won't explicitly list it, though for today, as an example, I just did); we covered a lot of material, some of it quite quickly.
Reminder: Please do make sure you understand exactly what HP is defined as; we'll be consistent regarding that through all our slides.
If you want examples of proving things undecidable, any standard textbook (but avoid Sipser for this as he uses a different notation) will have examples, but the most in sync with my approach (as long as their proofs don't make you think that pictures suffice as proofs) is Hopcroft-Ullman-1979.
(Actually, if you find Rogers hard going (it is!), and want something in addition to our slides, I commend to you as a source for examples regarding upper bounds in the arithmetical hierarchy lecture 35 (and in part lecture 36, which even does some hard completeness-proving, which most people think of as a type of lower-bound) of Dexter Kozen's book: Theory of Computation. (I think the library may well have it electronically, which is useful in these crazy times.) Kozen is at an easier reading/understanding level than Rogers. But to avoid confusion beware: Kozen (in addition to other unusual notations you'll see in that reading) defines HP in terms of halting, not (as we do) accepting; but in our course we'll ALWAYS use the accepting-based notion.)
In you group, you will master one chapter (the one that is the name of your group) of the Hem-Ogi textbook and prepare slides for and present as the April 12/14/19 lectures (if group Chapter 3) or as the April 21/26 lectures (if group Chapter 5) your slides on and lectures on that chapter. You do not have to cover the entire chapter. 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.
You WILL be graded on the quality of your entire unit (and that grade will be shaped by both the quality of the slides and the quality of the presentations, though those won't get separate grades from each other, probably). Some time after your final talk, after Sid and I have had time to talk with each other, so perhaps that evening or a day later, you'll meet with Sid and me for our feedback and to get your grade.
The details on how/what you'll hand in and do are as follows:
Please start right away, as digesting a chapter, making excellent slides, and presenting them in a clear, charismatic way to the class is a huge task. You are required to well BEFORE the day of your talk ("well before" means at latest Friday for a Monday talk, and at latest Monday for a Wednesday talk)---and you must schedule that ahead of time by agreement with the TA as to time/online-location---test-run your entire talk for the TA, who will give you his feedback on things (if any) that he sees that might be improved (e.g., things that are not clear). You will NOT be directly graded on that, as it is to give you helpful feedback; but if you don't have such a session your final score will be lowered by 10 points (e.g., a 98 would turn into an 88; that will be divided over your talks, that is, if you have 3 talks, each would have a 3.3333-point penalty if one run-through was missed, for example, and a 10-point penalty if all three were missed); and also, if you ignore problems the TA spots, that might lower the TA's assessment of the quality of your talk when you give it in class (and indirectly mine, since I too might notice the problems or notice them due to chatting with the TA after your talk about what grade it should give).
I'll assign the grade to your talk/slides (the ones presented in class), but will consult with the TA when doing so to get his input as to what he thinks of them.
You must also, no later than 200PM on the day of your talk, email to csc486staff "at" cs.rochester.edu your entire set of slides as a *pdf file*. Then, no later than the 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 csc486staff, cc'ed to every group member, 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 3 or 2 talks (depending on the group) should all look uniform within the group, e.g., you can have days 1 and 3 of your group be latex-based but day 2 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 1/2s or 1/3s 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 of course what chapter you are covering. (Note: The book has an online transparencies page. If your slides are strong, my book-coauthor or I might, IF it is ok with you, make your slides available to the public via that page. If we want to do that, we'll explicitly ask the group members---but only after you have already received your grade on the project; agreeing to let your slides be shared on the web is not required, and has no influence on your project grade, which will have been given before that anyway).
As to the talks, you have the entire 75-minute classes you were assigned, BUT you should if possible try to leave at least 10 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. Also, though you don't have to perfectly balance the number of minutes each of you speaks, unless someone in the group is extendedly sick, each group member should present at least some of at least one of your talks days (and I don't mean just standing up and saying "Hello"). More generally, please work carefully with your groupmates on preparing the talk, so you ALL are involved in the whole process, and are helping each other 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.), but may not actively seek help from any human---not even me or the TA (note the slight exception below regarding the TA)---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 (except for the help you'll get at the run-through from the TA, which is allowed, and indeed the run-through is required).
You have two possible paths to watch the talk.
(a) One path is to watch it live, when I give it at 12:20PM on Wed., April 14, at Theory Canal. (But as that is via Zoom, and you'll need to get the Zoom link. I don't want to post that on the web, but I will send it to you via BB announce on the evening of 4/12, and so it will be in BB on our announcements page's listing of such.
(b) The other path is to view the recording of my March 19th 2021 talk on this paper at the New York Colloquium on Algorithms and Complexity (NYCAC 20-21). That is currently being added to our course in Panopto, as the file/video "2021-04-12-quiz-and-talk-Online-Bribery-NYCAC-20-21-Lane-Hemaspaandra-20210319-1555-5" (it is a .mp4 file). There is no natural place for us to link to it from in our BB area, so I've linked to it from our "CSC 286/486 main-class-session recordings" page, though it in fact is not a main-class-session record. So, there, you will have THIS quiz/video (listed under 4/12), and will, when Sid posts it, also have the 4/12 in-class lecture by group Chapter 3.
Some of My Favorite Bits of Science Wisdom:
Other Odds and Ends (Mostly Quotations):