The course has concluded!
Thanks all for an interesting semester.
The final exam is here: finalexam.pdf
Hope everyone has an enlightening and fulfilling summer.
End of Course
Class 27: Wrap-up
Slides from class: class27.pdf
Some solutions and hints on the practice final are here: practicefinal-comments.pdf. (If there are questions about problems with incomplete solutions, we might add to this later.)
We won’t have the regular office hours schedule now that the end of classes has passed, but still have many office hours scheduled until the final exam on May 11. Please check the course calendar (and discord announcements) for information on office hours for this week and next week.
Preparing for the Final Exam
As scheduled by the Registrar, the final exam will be Thursday, 11 May, 2:00pm - 5:00pm in our normal classroom.
The final exam will cover everything we’ve done in the course, but with more emphasis on material that has been covered since the midterm.
There is now a Classes page that lists all the classes to make it easier for you to find specific content we’ve covered in class.
Like the midterm, you may prepare 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 your reference sheets together.
We have provided a practice final exam here: practicefinal.pdf
We will be posting solutions for these problems soon, but encourage you to try them yourself first under exam-like conditions.
Class 26: Cook-Levin Theorem
Slides from class: class26.pdf
Problem Set 10 is due on Friday, 28 April. The latex template is https://www.overleaf.com/read/ppdjrxcwqmnn.
Class 25: Probably Hard Problems
Slides from class: class25.pdf
Problem Set 10 is due on Friday, 28 April. The latex template is https://www.overleaf.com/read/ppdjrxcwqmnn.
Quiz 11 (which is a “make-up quiz”) is due 9:59pm on Wednesday, April 26.
Class 24: Complexity II
Slides from class: class24.pdf
Problem Set 10 is due on Friday, 28 April. The latex template is https://www.overleaf.com/read/ppdjrxcwqmnn.
Class 23: Complexity
Slides from class: class23.pdf
Problem Set 10 is due on Friday, 28 April. The latex template is https://www.overleaf.com/read/ppdjrxcwqmnn.
Class 22: Rice's Theorem
Slides from class: class22.pdf
Problem Set 9 is due on Monday, 17 April. The latex template is https://www.overleaf.com/read/mqwmbzjppfbv.
Class 21: Reductions and Recognizability
Slides from class: class21.pdf
Problem Set 9 is due on Monday, 17 April. The latex template is https://www.overleaf.com/read/mqwmbzjppfbv.
If the key opening door reduction isn’t exciting enough for you (or you’re just a fan of 1980s TV shows), you may want to watch this video: Proof by Reduction (from Fall 2020 course).
Class 20: Proving Uncomputability
Slides from class: class20.pdf
The learned video on computability from class is here.
If you want another presentation of the computability material in the textbook, try Dori-Mic and the Universal Machine!.
Problem Set 8 is due on Monday, 10 April. The latex template is https://www.overleaf.com/read/nhgcvwvnfvkh.