About the CS:5340 Final
The final for CS:5340 will be on Tuesday, Dec 12th from 10 am to noon
in 205 MLH.
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 25% of your grade and will be graded out of 250
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, 6, and 7.
In preparing for the exam, you can skip the following portions of
Chapters 4-7: Section 4.3.2, Sections 5.3 and 5.4, proof of Meyer's Theorem (Theorem 6.20),
Sections 6.6 through 6.8,
all of Section 7.2 except for Section 7.2.3 on polynomial identity testing,
and ection 7.5.3 and beyond.
There will be 4 problems on the exam. Here are more details of these problems.
-
As in the midterm. the first problem, worth 100 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 2-sentence justification for your answer.
These complexity theoretic claims will span all of the material covered during the semester.
-
The next two problems, each worth 50 points, will test your understanding
of the text-book proofs of two of the following ten theorems: Theorems
4.13, 4.14, 4.18, 5.4, 5.12, 6.6, 6.13, 6.18, 6.19. 7.14.
As in midterm Problems 3 and 4, I will ask whether the proof continues to work if we modify the theorem
statement or some step in the proof; you will have to justify your answer.
-
The last problem will be a variant of a problem assigned for homework or a variant
of a problem from Chapter 7 practice problems (to be assigned).
So you want to make sure that you know how to solve all assigned homework problems before
you get to the final.