|
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, Fredman-Tarjan)
|
Presentation (pptx)
|
Problem Set 1
Due: November 23
|
|
Minimum Spanning Trees
Verification
Linear time verification algorithm
(Komlós, King, Hagerup)
Checking meldable heaps (Bright-Sullivan)
LCA queries (Bender-Farach Colton)
Range Maxima (Vuillemin)
|
Presentation (pptx)
|
Problem Set 2
Due: December 7
|
|
Minimum Spanning Trees
Randomized linear time algorithm (Karger-Klein-Tarjan)
|
Presentation (pptx)
|
|
Minimum Directed Spanning Trees
Edmonds’ algorithm (Chin-Liu,
Edmonds, Bock)
Efficient implementations (Tarjan, Gabow-Galil-Sepncer-Tarjan)
|
Presentation (pptx)
|
|
Shortest Paths
Goldberg's scaling algorithm
|
Presentation (pptx)
|
Problem Set 3
Due: January 9
|
|
Maximum non-bipartite matching
Edmonds' blossom shrinking
algorithm
Efficient implementation
|
Presentation (pptx)
|
|
Maximum weighted non-bipartite
matching
|
Presentation (pptx)
|
Problem Set 4
Due: February 1
|