Advanced Topics In Algorithms

AY2015/2016 Semester 1

Advanced Analysis: recurrences and master theorem, potential functions, amortized analysis, online and offline algorithms. Advanced Algorithmic Strategies: dynamic programming, preprocessing, randomization, backtracking, branch-and-bound. Algorithms for Selected Problems: computational geometry, maximum flow, algorithms for symbol sequences; Computational Complexity: lower-bounds, NP-completeness and problem reduction. Approaches for Hard Problems: heuristic and approximation algorithms, randomized algorithms.