This is an advanced course in the design and analysis of algorithms. It reviews in particular fundamental paradigms like flows and matchings, linear programming,... NP-completeness is briefly rediscussed with a focus on polynomial reductions. Several ways to analyze algorithms are considered: notions of complexity, like worst case, average case, smooth analysis, amortized or parametric complexity (potentials, treewidth, or kernelization); measures of output quality (approximation factor for combinatorial optimization, competitivity for online algorithms).

Requirements : Minimal prerequisite are: some elements of algorithmics (arrays, lists, trees; sorting algorithms), of complexity (upper and lower bounds on the worst case complexity of sorting), and some familiarity with mathematical tools (induction, etc). Having taken INF423, INF431 or some computer science course of similar level is useful.

Evaluation mechanism : Written exam at the end of the course.

Last Modification : Tuesday 20 March 2012