CS 474 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.
Credit units: 3 ECTS Credit units: 5, Prerequisite:
CS 473.
|
|
|
Bilkent University Main Page
Last regenerated automatically on December 30, 2024 by OAC - Online Academic Catalog Software
|
|
