This course covers advanced techniques of algorithm design and analysis. The course begins with a quick review of some major notions of algorithmics, such as linear programming or NP-hardness and polynomial reductions. Beyond worst case analysis, several alternative approaches are discussed, be it in terms of complexity: worst case, in average, amortized, smoothed or parametric; or in terms of output quality measures: optimality, approximation factor for optimization, competitivity for online algorithmic. Featured topics include potentials, preprocessing and kernelization, treewidth, primal-dual algorithms, SAT solvers.
Evaluation modalities: written exam at the end of the course
Course language: English unless all students prefer french.
Training ressources: they are on the moodle page but an old page gives you an idea of the style of the course
ECTS credits: 4
