ANALYSIS OF ALGORITHMS (0368.4222.01)
February-June 2014, Tel Aviv University
Lecturer: Uri Zwick

Exam: Thursday, June 19, 2014

List of subjects

Minimum Spanning Trees

· Basic properties: the blue and red rules

· Classical algorithms: Kruskal, Prim, Boruvka

· The randomized linear time algorithm of Karger, Klein and Tarjan

Minimum Directed Spanning Trees

· Edmonds' cycle contraction algorithm

· Tarjan's implementation

Global minimum cuts

· The deterministic algorithm of Stoer and Wagner

· The randomized algorithms of Karger and Stein

Motwani & Raghavan: Randomized Algorithms, pages 289-295.

Dynamic All-Pairs Shortest Paths

· The algorithm of Demetrescu and Italiano

Maximum Matchings in Bipartite and General Graphs

Weighted Maximum Matchings in Bipartite and General Graphs

Past exams