Exam 3 Comments
Exam 3 and solutions to Exam 3 are posted here: Exam 3 Exam 3 Comments Oral Exam Requests. Out of 157 students who filled in something we could interpret as a grade for the Oral Exam Request on the last page, there were 40 who filled in the exact grade they received in the course, 109 who filled in a lower grade than they received (of whom 50 received at least a full letter grade higher than the minimum grade entered), and 8 who filled in a higher grade than the grade we determined was appropriate (and have the opportunity to improve their grade by doing an oral exam).Class 24: Conclusion
Exam 3 will be in class on Wednesday.
Class 23: More NP Completeness
TCS Chapter 14: NP, NP completeness, and the Cook-Levin Theorem
Preparing for Exam 3
Exam 3 will be Wednesday, 4 December at the normal class time in the normal classroom. We will aim to start the exam right at 3:30pm, so you will benefit from arriving early for class Wednesday to be settled and ready to start the exam. This is the final exam for the class and we will not use the registrar-scheduled final exam time, but recall from the course syllabus that there will still be an opportunity for students who feel they were “not be able to demonstrate their best ability during a 75 minute in-class exam, … to request an oral final exam to be scheduled with one of the instructors during the exam period.Class 22: NP Completeness
TCS Chapter 14: NP, NP completeness, and the Cook-Levin Theorem
Cook’s Paper
Levin’s Paper (Translated)
Class 21: Is Omniscience Helpful?
TCS Chapter 14: NP, NP completeness, and the Cook-Levin Theorem
The Longest Path (Lyrics by Daniel Barrett)
Problem Set 7
Problem Set 7: Is P a proper subset of NP?
Problem Set 7 is available here: ps7.pdf (you will also need the ps7.zip file). It is due on Tuesday, 26 November at 7:29pm.
Note that PS7 is considerably longer than previous problem sets, and you have a longer time period to complete it. I covers a lot of challenging material from recent (and upcoming) classes and book chapters 11-14.
Class 20: Polynomial-Time Reductions
TCS Chapter 11: Efficient computation
TCS Chapter 12: Modeling running time
TCS Chapter 13: Polynomial-time reductions
Class 19: Turing maching running time
TCS Chapter 11: Efficient computation
TCS Chapter 12: Modeling running time