The course intends to deal with advanced aspects of algorithm: design and analysis including data structures, analysis and lower bound proofs, amortized complexity of algorithms.
Fibonacci heaps and self-adjusting search trees, Splay trees, linking and cutting trees.
State-of-the-art algorithms for minimum spanning trees, shortest path problem. Network flows -- preflow-push algorithms, max flow algorithm, and scaling algorithms.
Matching, blossoms, Micali-Vazirani algorithm.
Lower bound theory for parallel computations.
R. E. Tarjan.Data structures and Network Algorithms, SIAM Press, 1983.
J. H. Hastad.Computational Limitations for Small-Depth Circuits, MIT Press, 1987.
K. Melhorn.Data Structures and Algorithms, Vol. 1: Sorting and Searching, Springer Verlag, 1984.
K. Melhorn.Data Structures and Algorithms, Vol. 3: Multi-dimensional Searching and Computational Geometry, Springer Verlag, 1984.