structure
- 7 questions, answer 5
- skyline problem eliminated
what’s on it
divide and conquer
- closest pair of points
greedy
- Huffman coding
- scheduling (a3 question is important)
- stable matching
graph
- data structures
- graph search/traversal
- whatever first
- dfs
- bfs
- minimum spanning tree
- boruvka
- prim
- kruskal
question style
- if slides have proof → learn it
- if slides don’t have proof → don’t need to know it
- will probably ask proof for qreedy algs
- if asked to give a stable matching, you need to include all matches instead of a single (1,A)