This course is directed to 3rd year students in the Ingénieur Polytechnicien Program.
This course covers advanced techniques in the design and analysis of algorithms. The course begins with a quick overview of some of the main paradigms in algorithmics, including flows and matchings, as well as linear programming. It then briefly revisits NP-completeness, emphasizing the importance of polynomial reductions. Beyond worst-case analysis, several possible approaches to algorithm analysis are considered. This includes exploring complexities such as average-case, amortized, or parametric. Additionally, the course delves into approximation algorithms with notions such as optimality, approximation factor for optimization, and competitiveness for online algorithms. This will be an opportunity to introduce concepts such as potential, kernel, and tree-width, among others.