Dynamic Programming
 - Recursion + memoization = dyanamic programming
 - Ability to convert recursive algorithm into iterative algorithm
   to avoid recomputing solutions
 - Run time and space analysis
 - Reducing space if only value needed

Greedy Algorithms
 - exchange argument based proofs for greedy algorithm

Minimum Spanning Trees
 - definition of problem
 - cut and cycle properties, safe and unsafe edges
 - correctness of MST algorithms via safe/unsafe characterization
 - Kruskal, Prim, and their implementation and running time
 - Union Find data structure and knowledge of implementations discussed
   in lecture notes.
 - Basics of amortized analysis

Basics of randomized algorithms
 - definition of a randomized algorithm
 - basics of discrete probability, especially expectation
 - randomized quick sort and selection
 - basic knowledge of hashing but no need to know analysis of
   universal hashing.

Basics of network flow
 - definitions of flows/cuts
 - Ford-Fulkerson algorithm for finding a maximum flow
   via augmenting paths in residual graph
 - Proof of maxflow-mincut theorem via FF algorithm
 - Integrality of flow when capacities are integer
 - Knowledge of polynomial time variants of FF and their running time.
 - Finding a mincut through a max flow

Applications of network flow:
 - Bipartite matching
 - Baseball elimination
 - Project selection


These topics cover what we discussed in lecture from midterm 1 to
Tuesday's lecture (lecture 19). Applications of network flows are in
the midterm (the previous version of this file was from previous
semester - our midterm is slightly later than the previous
sememster). In any case, the applications of network flow is not the
emphesize of this midterm.