Final Exam Preparation
The Final Exam will be Thursday, 7 December, 9am-noon in the normal classroom.
The final will cover everything in the course, with an emphasis on the most important concepts that have appeared in at least two places.
Most of the questions on the final will be small variations on problems you have already seen on previous exams or problem sets. Doing well on these questions will make a strong case for earning at least a B in the class. A few of the problems will be designed to see how well you can use concepts you have learned in the class to solve problems unlike ones you have already seen. Doing well on many of these questions will make a strong case for earning an A in the class. (Of course, we will also take into account your performance on other parts of the class including the exams and problem sets.)
The format will be fairly similar to Exam 1 and Exam 2, but because of the extended time for the final, and the desire to give as much opportunity as possible for students to demonstrate what you can do, will be a bit longer than those exams.
As with Exam 1 and Exam 2, you will be permitted to use a single paper page of notes that you prepare and bring to the exam, but no other resources. It is fine to collaborate with others to prepare your notes. The page should be no larger than a US Letter size page (8.5 x 11 inches), and you may write (or print) on both sides of the page.
Expected Problems
Although the exam covers the whole class, you should not be surprised if it includes problems for you to demonstrate:
Your understanding of logical formulas, inference rules, and an ability to reason about and manipulate formulas using quantifiers.
Your fluency with standard proof techniques including proof-by-contradiction.
Your understanding of well-ordering and how to construct proofs using the well ordering principle.
Your understanding of sets, how the set operators are defined, and what they mean.
That you can do a regular induction proof similar to ones you have seen on previous exams very well. That you can do an induction proof that requires some creativity to define a good induction predicate and then to complete the proof.
Your understanding of state machines, and ability to use the invariant principle to prove a property of the reachable states for a given state machine.
Your understanding of recursive data types, ability to define functions on recursive data types, and to use structural induction to prove a property about all objects of a recursive data type.
Your understanding of infinite cardinalities including the ability to determine if a set is countable or uncountable, and to support your answer with a convincing proof.
Your understanding of number theory, including the ability to reason about properties of prime and composite numbers, Abelian groups and fields.
Practice Exam
The exam from last year’s course is available here: [PDF]. All of the questions from last year’s final would be reasonable questions for this year’s final except for 6d (we did not cover Turing machines this year) and 12. Last year’s final doesn’t include any questions on number theory since we didn’t cover that enough last year, but your final is likely to include a few number theory questions that you will be well-prepared for if you understand PS9. Otherwise, the content and format of this final is similar to what you should expect on your final.
You are strongly encouraged to try to solve the problems yourself, before consulting the Practice Final Solutions.