ANALYSIS OF ALGORITHMS
(0368.4222.01)
October 2017 – January 2018
Lecturer: Uri Zwick

Minimum Spanning Trees
Classical deterministic algorithms (Kruskal, Prim, Borůvka)
More efficient algorithms (Yao, FredmanTarjan)

Presentation (pptx)

Problem Set 1
Due: November 23

Minimum Spanning Trees
Verification
Linear time verification algorithm
(Komlós, King, Hagerup)
Checking meldable heaps (BrightSullivan)
LCA queries (BenderFarach Colton)
Range Maxima (Vuillemin)

Presentation (pptx)

Problem Set 2
Due: December 7

Minimum Spanning Trees
Randomized linear time algorithm (KargerKleinTarjan)

Presentation (pptx)

Minimum Directed Spanning Trees
Edmonds’ algorithm (ChinLiu,
Edmonds, Bock)
Efficient implementations (Tarjan, GabowGalilSepncerTarjan)

Presentation (pptx)

Shortest Paths
Goldberg's scaling algorithm

Presentation (pptx)

Problem Set 3
Due: January 9

Maximum nonbipartite matching
Edmonds' blossom shrinking
algorithm
Efficient implementation

Presentation (pptx)

Maximum weighted nonbipartite
matching

Presentation (pptx)

Problem Set 4
Due: February 1
