Algorithms II

Augmenting Data Structures: augmenting red-black trees, dynamic order statistics, interval trees. Advanced priority queue implementations: binomial heaps, Fibonacci heaps. Data structures for disjoint sets: linked list representation, analysis of weighted union heuristic; disjoint set forests, analysis of union-by-rank with path compression. Elementary graph algorithms: breadth-first search, depth-first search (DFS), use of DFS for topological sort and strongly connected components, correctness proofs. Minimum Spanning Trees (MST): generic MST algorithm, proof of correctness, the algorithms of Kruskal and Prim. Single source shortest paths: Bellman-Ford algorithm, Dijkstra's algorithm, difference constraints and shortest paths, proofs of shortest-paths properties. All-pairs shortest paths: two DP formulations; matrix multiplication and Floyd-Warshall algorithm.,transitive closure of a directed graph, Johnson's algorithm for sparse graphs. Maximum Flows: flow networks, Ford-Fulkerson method, maximum bipartite matching, push-relabel algorithms.