CS 645: Topics in Design and Analysis of Algorithms

Course Contents:

Introduction.

Linear time special cases for Disjoint set Union-Find algorithms.

Topics in Computational Geometry like Selection algorithms and application to convex hull (ultimate convex hull algorithm), linear programming in two and three dimensions.

Topics in Algorithmic Graph Theory like Planar graph separators.

Integer sorting and improved algorithms for shortest paths and minimum spanning tree (general and integer weights).

Polynomial time algorithms for matching and minimum cost network flow problems.

Scaling algorithms for network flow problems.