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 17). -------------------------------------------------------------------- -------------------------------------------------------------------- -------------------------------------------------------------------- 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 --------------------------------------------------------------------