CS 474 Algorithms II

Augmenting Data Structures: augmenting redblack 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 unionbyrank with path compression. Elementary graph algorithms: breadthfirst search, depthfirst 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: BellmanFord algorithm, Dijkstra’s algorithm, difference constraints and shortest paths, proofs of shortestpaths properties. Allpairs shortest paths: two DP formulations; matrix multiplication and FloydWarshall algorithm.,transitive closure of a directed graph, Johnson’s algorithm for sparse graphs. Maximum Flows: flow networks, FordFulkerson method, maximum bipartite matching, pushrelabel algorithms.
Credit units: 3 ECTS Credit units: 5, Prerequisite:
CS 473.



Bilkent University Main Page
Last regenerated automatically on October 11, 2024 by OAC  Online Academic Catalog Software

