About the Final Exam
- The exam will be a 3-hour takehome exam taken under the HMC Honor
Code.
- The only permitted materials are your class notes, your homework
solutions, and the solution sets that were distributed in
class and one 8 by 11 sheet of paper (front and back) with
additional notes that you prepare in advance. No other materials
(animate or inanimate) are permitted.
- The exam will comprise a collection of short problems - much
smaller in depth than a typical homework or previous takehome exam
problem. However, to encourage you to review the material,
there will be one problem on the exam that is very nearly identical
to a previous exam problem or a problem that we solved in class.
- The exam will cover material spanning the entire course.
- You may pick up the exam on Monday, May 11 in the bin outside of
Ran's office door anytime after 8 AM. Then, give yourself a
consecutive 3 hour block of time to take the exam. At the end of 3
hours, seal the exam in the envelope and it slide it under Ran's
door. In order to allow you "transportation
time", you may return the exam up to 4 hours after picking it up.
Exams must be returned by 5 PM on Monday, May 11.
- Seniors: You may make special
arrangements with me to take the exam on May 6, 7, or 8. Pomona
seniors need to take the exam on May 6 or 7 in order to have grades
to the Pomona Registrar on May 8.
Below is a list of the major topics in this course. This list is
intended to help you review in preparation for the exam. It is not
intended to be a comprehensive list of every topic studied. Reviewing
your class notes is the best way to make sure that you've examined all
of the material.
Foundations
- Proofs of correctness using mathematical induction and
invariants
- Basic identities (geometric series, etc.) and properties of logarithms
- Big-Oh, big-Theta, and big-Omega and when each one is appropriate
- Divide-and-conquer and recurrence relations
- Dynamic programming
- Greed and how to prove that a greedy algorithm is correct
- Amortized analysis: Aggregation, accounting, and the potential method
Abstract Data Types and Data Structures
- Priority queues and heaps
- Dictionaries and Red-black tree, B-trees, and lazy amortized
trees
- Union-Find
Fundamental Graph Algorithms
- Representations of graphs and their impact on algorithm efficiency
- Depth-first search, breadth-first search, and topological
sorting
- Shortest path algorithms (Bellman-Ford, Dijkstra,
Floyd-Warshall, Johnson re-weighting scheme) and their proofs of correctness
- Minimum Spanning Trees: The "Big Theorem", Prim and Kruskal, proofs of
correctness using the theorem, and data structures used to support
these algorithms
- The theory of network flow, the Ford-Fulkerson algorithm and
its proof of correctness
NP-Completeness and Approximation
- Decision problems, optimization problems, definitions of P and
NP, and NP-completeness
- Proofs of NP-completeness
- Approximation algorithms for NP-complete problems using the
"proxy" method
- Self-reducibility and its significance
Advanced Topics
- Parallel algorithms for shared and distributed memory models
- Online algorithms, competitive analysis, the k-server problem,
and other basic online algorithms
- Basic ideas from computational geometry