ANALYSIS OF ALGORITHMS  (0368.4222.01)
Lecturer: Uri Zwick

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

Presentation (pptx)

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)

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)

Minimum Mean Weight Cycles
Karp’s algorithm

Presentation (pptx)

Min Cost Flow
A strongly polynomial time algorithm

Presentation (pptx)
Lecture Notes (pdf)

Maximum non-bipartite matching
Edmonds' blossom shrinking algorithm
Efficient implementation

Presentation (pptx)

Maximum weighted non-bipartite matching

Presentation (pptx)

 

Some previous exams
(Note: The material covered in previous years are not identical.)

Exam 2009/2010a
Exam 2009/2010b

Exam 2010/2011a
Exam 2010/2011b

Exam 2013