About the 22C:131 Final

• The final for 22C:131 will be on Tuesday, Dec 11th from 8 pm to 10 pm in the classroom, CB E203. This is an open notes (book) exam, so feel free to bring books, handwritten notes, printouts of online notes and webpages, etc., to the exam. The exam is worth 30% of your grade and will be graded out of 300 points. While the exam is technically over all of the material we have covered this semester, it will focus on the material in Chapters 4, 5, and 7. In preparing for the exam, you can skip Sections 4.3.2 (NL = coNL), 5.3 (Alternating TMs), 5.4 (Time vs Alternations), 5.5 (Oracle machines), 7.2 (Examples of PTMs), and 7.5.1 (BPP languages have poly-sized circuits). After the midterm, I covered a little bit of material that is not in the textbook, including the PSPACE-completeness of GEOGRAPHY GAME, a general treatment of the most popular tail inequalities, etc. You are responsible for all of this material and in general any material discussed in the lectures, independent of whether it appears in the textbook.

• There will be 4 problems on the exam. As in the midterm. the first problem (worth 90 points) will consist of complexity-theoretic claims and for each claim, you will have to say whether the claim is known to be true, known to be false, or not known to be either. If your answer is true or false, you will have to provide a 1-sentence justification for your answer. These complexity theoretic claims will span all of the material covered during the semester. The remaining 3 problems (each worth 70 points) will each ask for a relatively short proof of a claim based on material from each of Chapters 4, 5, and 7. These problems will either directly come from chapter-end exercises or will be minor variants of chapter-end exercises. So one good way to prepare for the exam is to work out relevant chapter-end exercises.