Algorithms and complexity

This course provides the foundations for the design and analysis of computational methods, that is the processing of information by physical systems. It covers the efficient organization of computation (algorithms) as well as the limits to that efficiency (complexity theory).

This course consists of seven lectures on methodologies and two lectures on case studies. The exercise classes are on paper.

Lecture 1. Case study: ressource allocation and Gale-Shapley algorithm

Ressource allocation problem, notion of computational problem, stable matching problem, Gale-Shapley algorithm, analysis of and variations on that algorithm, implementation in the Parcoursup platform.

Lecture 2. Classical models of computation

Notions of computer architecture, RAM models, asymptotic worst-case complexity.

Lecture 3. Design of recursive algorithms

Simplify and delegate, dichotomy, divide and conquer, backtracking.

Lecture 4. Asymptotic worst-case complexity of recursive algorithms

Analysis of execution trees, master theorem, Akra-Bazzi theorem.

Lecture 5. Case study: voting systems

Notion of social choice, Gibbard–Satterthwaite theorem, vote counting methods: Copeland, Minimax, Kemeny-Young, ranked pairs, Schulze.

Lecture 6. Complexity lower bounds

Notion of complexity of a problem, adversarial arguments, decision trees.

Lecture 7. Reduction between problems

Coloring problem, reduction mecanism and lower bound propagation.

Lecture 8. NP-hardness

Satisfiability problem, P and NP complexity classes, Cook-Levin theorem, NP-hardness and NP-completeness.

Lecture 9. Quantum model of computation

Qbit and mesure, quantic gates, no-cloning theorem, basic circuits, Deutsch–Jozsa algorithm.

The efficiency of an algorithm method and the hardness of a computational problem