CS 647: Advanced Topics in Algorithms and Data Structures

Course Contents:

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.

Books and References:

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.

Research papers.