Final Exam

The final will take place in CSE2 G01 2:30-4:20 on Monday March 13th.

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.
• Define and 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 linear programming lectures)
• But, we will consider the amount of practice you've had with various topics when designing problems.
• For example, you have never designed a linear program on a homework, so we are unlikely to ask you to design one from scratch on the exam.
• 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 March 9th will be going through not-yet-covered problems as a way to review.
• There will be a review session on Satruday March 11 from 1:30-3 in CSE2 G01 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.