CS647A - Advanced Topics In Algorithms & Data Strcutures

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 pre flow push algorithms, max flow algorithm, and scaling algorithms. Matching, blossoms, Micali Vazirani algorithm. Lower bound theory for parallel computations.