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

Lecture notes


Minimum Directed Spanning Trees

         Edmonds' cycle contraction algorithm

         Tarjan's implementation

Lecture notes

Some slides

Solution to selected exercises

Global minimum cuts

         The deterministic algorithm of Stoer and Wagner

         The randomized algorithms of Karger and Stein 

Lecture notes

Problem Set

Link to the Karger-Stein paper

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

Dynamic All-Pairs Shortest Paths

         The algorithm of Demetrescu and Italiano

Some slides


Problem Set

Link to the Demetrescu-Italiano paper

Maximum Matchings in Bipartite and General Graphs

Lecture notes (including exercises)


Weighted Maximum Matchings in Bipartite and General Graphs


Past exams

Exam 2009/2010a
Exam 2009/2010b

Exam 2010/2011a
Exam 2010/2011b

Exam 2013