ANALYSIS OF ALGORITHMS (0368.4222.01)

October 2009 – January 2010, Tel Aviv University
Lecturer: Uri Zwick

Minimum Spanning Trees

· Basic properties: the blue and red rules

· Classical algorithms: Boruvka, Kruskal, Prim

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

· The linear time verification algorithm of Komlos (and King)

Link to the Karger-Klein-Tarjan paper
Link to King's paper

Motwani & Raghavan: Randomized Algorithms, pages 296-302.

Lecture notes

Problem Set 1

Global minimum cuts

· The randomized algorithms of Karger and Stein

Lecture notes

Problem Set 2

Link to the Karger-Stein paper

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

Dynamic All-Pairs Shortest Paths

· The algorithm of Demetrescu and Italiano

Lecture notes

Problem Set 3

Link to the Demetrescu-Italiano paper

Maximum matching in general graphs

· Augmenting paths and alternating trees

· Edmonds' blossom shrinking algorithm

Lecture notes

Mehlhorn & Naher: LEDA – A platform for combinatorial and geometric computing, pages 393-413.
Ahuja , Magnanti, Orlin: Network flows, Chapter 12.

Matrix-multiplication based graph algorithms

Presentation

Past exams

Exam 2007a
Exam 2007b
Exam 2008a
Exam 2008b
Exam 2009a