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

1. R. E. Tarjan.Data structures and Network Algorithms, SIAM Press, 1983.
2. J. H. Hastad.Computational Limitations for Small-Depth Circuits, MIT Press, 1987.
3. K. Melhorn.Data Structures and Algorithms, Vol. 1: Sorting and Searching, Springer Verlag, 1984.
4. K. Melhorn.Data Structures and Algorithms, Vol. 3: Multi-dimensional Searching and Computational Geometry, Springer Verlag, 1984.
5. Research papers.