**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

Solution to selected exercises

**Global minimum cuts**

·
The deterministic algorithm of Stoer and Wagner

· The randomized algorithms of Karger and Stein

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

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**

Exam
2009/2010a

Exam
2009/2010b

Exam
2010/2011a

Exam
2010/2011b