Format

The final will be an in-class exam with no collaboration allowed. All work must be done individually, and you should not discuss the exam with anyone except the course staff.

• Date: Saturday, April 30th, 10a–2pm
• Location: Churchill 101 for M/Th, Churchill 103 for Tu/Fr

Topics

• Recurrences, Master’s theorem
• Greedy algorithms and exchange arguments
• Dynamic programming for graph problems
• Shortest paths: unit edge weights, non-negative weights, negative weights, all-pairs
• Minimum Spanning trees
• Maxflow, mincut
• Bipartite matching
• Other applications of maxflow, edge-disjoint paths, etc
• Stable matching
• NP-reductions
• Data structures
  • Main performance claims of a VEB queue
  • How the insert works

Ways to prepare

• Be sure to review the solutions to all of the homework problems.
• Look over the problems presented in lecture. Ask yourself, if you were presented this problem, would you know how to derive the proposed solution? If not, where do you get stuck? You can use the rest of the slides to check yourself. We have 20+ examples of problems that you should be able to solve by yourself.
• You can look over the problems in CLRS and KT textbooks in the Graphs, Flows, and Stable matching sections and see if you can solve them.
• Take a look over the quiz questions that I’ve asked. Can you answer them?