This is an archived page from the Fall 2019 version of the course.
For the latest version, see https://uvatoc.github.io.

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

We realize that this was not quite a “tell us the grade you think you deserve” question since some people may find having to do an oral exam a non-neutral experience, but we these results do give us some confidence that most students will consider their course grade fair.

Office Hours Tuesday. If you would like to retrieve your exam, or have anything else you’d like to discuss, we will have our normal office hours on Tuesday (Dave, 9-11am in Rice 507; Nathan, 4-6pm in Rice 209).


Class 24: Conclusion

Exam 3 will be in class on Wednesday.

Slides
Video


Class 23: More NP Completeness

Slides
Video

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

Exam 3 will cover material from the entire course, with an emphasis on material that has been covered since Exam 2 (Classes 17-24, Problem Set 7, and Chapters 11-14 in the TCS book). It will definitely also include some problems on earlier topics such as Boolean circuits, infinite cardinalities, and computability, and some questions designed to ask you to synthesize things you have learned throughout the course.

As a reminder from the syllabus, you may construct a one-page (letter-size, two-sided) reference sheet for use during the exam, but all other resources are forbidden (no internet, textbook, other humans, magnification instruments, etc.). We expect that students will benefit from thinking about what to put on your reference sheet in preparing for the exam, and you may work with anyone you want (including other students in the class) to prepare a reference sheets together.


Class 22: NP Completeness

Slides
Video

TCS Chapter 14: NP, NP completeness, and the Cook-Levin Theorem

Cook’s Paper
Levin’s Paper (Translated)