Advanced Algorithms

A comprehensive overview of the most commonly used approaches for approximate solution of NP-Hard problems, including linear programming, dynamic programming, and greedy algorithms. A survey of common algorithms including cache-aware algorithms, randomized algorithms, network flow algorithms, and online algorithms. This course takes an ‘experimental algorithms’ approach to educating students on augmenting theoretical results with empirical methods for the design of algorithms that are effective in practice.

Learning Objectives

1. Given an NP-hard combinatorial optimization problem, design an approximation algorithm for it and determine its approximation factor.
2. Explain how blocking can be used to reduce the number of cache-misses in big-data problems.
3. Analyze the time complexity of randomized algorithms.
4. Given a stream of data and an optimization problem, design an algorithm that can determine a good solution.
5. Given a problem, explain how network flow algorithms can be used to solve it.
6. Given a practical problem, determine suitable algorithms to solve it, produce an implementation that is effective in practice, and explain the reasons for its effectiveness.