CS-627 / 2 crédits
Enseignant: Svensson Ola Nils Anders
Only this year
This course covers numerous powerful algorithmic techniques (greedy, local search, linear programming, multiplicative weight update, ...). The concepts are studied in clean and simple settings so as to emphasize the main algorithmic ideas over problem specific details.
The goal of this course is to give starting PhD students a toolbox of algorithmic techniques. The course emphasises the illustration of the main ideas of these techniques and we will apply them in the simple and clean setting of the set cover problem. The algorithmic techniques that we plan to cover include:
- Greedy algorithms
- Local search algorithms
- Linear programming
- Randomized rounding (independent, threshold, exponential clocks)
- Duality (primal-dual algorithms, dual fitting, and the use of complementarity slackness)
- Multiplicative weight update
- Online algorithms in adversarial and random order streams (primal-dual, potential function, and projection based).
In addition, to attending the lectures, students are required to submit a project report where they apply one of the algorithmic techniques in a more complex setting.
Algorithms, set cover
Undergraduate algorithms and basic discrete math/probabilities
Learning Outcomes: To apply a rich algorithmic toolbox in order to solve their favorite problems.
Dans les plans d'études
- Forme de l'examen: Rapport de TP (session libre)
- Matière examinée: Algorithmic Toolbox
- Cours: 20 Heure(s)