The course will cover some basic material encountered at the relevant undergraduate courses on data structures and algorithms plus more advanced material on topics such as network flows, linear programming, computational geometry and NP-completeness. There will be emphasis on techniques such as greedy and dynamic programming. Amongst other topics, the course covers the following: • Binomial heaps, an example of worst-case analysis • Amortized analysis • Fibonacci heaps, an example of amortized analysis • Hash tables, an example of randomized analysis • Greedy algorithms and matroids • Dynamic programming and all-pairs shortest paths • Maximum flow • Linear Programming and Duality •Primal-Dual schema as an algorithmic design tool • Approximation algorithms
