Spring 2015: Midterm 2 topics
-----------------------------
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
These topics cover what we discussed in lecture from midterm 1 to
Tuesday's lecture (lecture 18, Tuesday March 31, 2015).
--------------------------------------------------------------------
--------------------------------------------------------------------
--------------------------------------------------------------------
Not covered this semester:
Applications of network flows are NOT in the midterm (the previous
version of this file was from previous semester - our midterm is
slightly earlier than the previous sememster). In any case, the
applications of network flow is not in this midterm.
Applications of network flow:
- Bipartite matching
- Baseball elimination
- Project selection
--------------------------------------------------------------------