Bilkent University Logo

Bilkent University

Online Academic Catalog

Undergraduate and Graduate Programs 2024-2025


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 October 11, 2024 by OAC - Online Academic Catalog Software