Advanced Algorithms

3 units

Provides a broad coverage of fundamental algorithm design techniques with the focus on developing efficient algorithms for solving combinatorial and optimization problems. The topics covered include: review of greedy algorithms, dynamic programming, NP-completeness, approximation algorithms, use of linear and convex programming for approximation, and on-line algorithms. Throughout this course there is an emphasis on correctness proofs and the ability to apply the techniques taught to design efficient algorithms for problems from a wide variety of application areas.