Final Exam

The final will take place in Kane 220 2:30-4:20 on Monday December 12th.

Logistics

• You will be allowed one piece of 8.5x11 inch paper of handwritten notes.
• We will also provide this reference sheet for the final (we will hand you a copy of this sheet; your extra handwritten notes should contain content beyond this piece of paper).

Topics List

We may ask you to

• design an algorithm for a problem, and possibly prove it correct.
• prove a given algorithm correct
• prove a given algorithm incorrect (e.g., by producing a counter-example)
• Design a polynomial time reduction and justify its correctness.
• Justify the approximation ratio of an approximation algorithm.
• Analyze the running time of your algorithm or a given algorithm
• Recall and apply properties of given algorithms from class (e.g., remember what proposer-optimality is, and what it means for Gale-Shapley)
• Consider implications of NP-completeness and related topics (e.g., realize whether a reduction would prove P=NP).

You are responsible for:

• All lecture conent from the course.
• This includes lectures that didn't have corresponding homework problems (like the randomized algorithms lecture and the linear programming lecture)
• But, we will consider the amount of practice you've had with various topics when designing problems.
• For example, you have never designed a randomized algorithm on a homework, so we are unlikely to ask you to design a randomized algorithm from scratch.
• All sections
• All homeworks
• The exam is cumulative (content from the whole course can show up), but we will focus on content after the midterm.

Resources and Planning

• Section on Thursday December 8th will be going through not-yet-covered problems as a way to review.
• There will be a review session on Sunday December 11 from 11-1 going through the sample final. We intend to record the session and post to panopto.

We strongly recommend reading solutions to prior homework problems. It is common to have multiple correct approaches to a problem, and a common source of problems is modifying prior problems from class; knowing our solution (as well as yours) can be helpful for these problems

Here is a sample final. We strongly recommend taking this exam under exam conditions. Here are the solutions to the sample final.