All posts by date
Approximations of the Euclidean metric traveling salesman problem
Back in the good ol’ agrégation days, I remember I used as développement^{1} a nice 2approx algorithm for the traveling salesman problem where the weights on the edges are given by the Euclidean distance between nodes.

This must mean nothing to nonFrench people but anyway. ↩
Count particular rectangles in a matrix
Given a matrix with distinct values, a rectangle consists of 4 cells at the intersection of two distinct rows and two distinct columns. It is good if the largest 2 values of the 4, are on the same row or the same column. Count the number of good rectangles in linear time, in the size of the matrix.
Suffix Array
Given a string s, sort all cyclic shifts of s. Formally produce a table p such that p[j]=i if s[i:]+s[:i] has rank j among all cyclic shifts.
PC Trees
A data structure representing all permutations satisfying constraints of the form: for a given set $S\subseteq\{0,1,\ldots,n1\}$ the elements of the permutations on $\{0,1,\ldots,n1\}$ have to be consecutive in circular manner.
Largest rectangle under an histogram
You are given an histogram and want to identify the area of the largest rectangle that fits under the histogram.
AI and LLM in education
In my new role as scientific advisor at the French Ministry of Education, I have recently been looking for metaanalyses and RCTs about impact of AI (and LLMs) in education.
Cover trees
Cover a tree with paths or caterpillars.
Meilleur developpeur de France 2023
Le 9 mars 2023 avait lieu la compétition Meilleur Développeur de France 2023. Les algorithmes nécessaires sont résoudre les problèmes sont assez simples, mais il faut coder rapidement. Après coup, et à tête reposée, voici comment on aurait pu résoudre certains des problèmes.
SWERC 2022 Practice Session  Bloggers
Abstract: Maintain two tables $t_0$, $t_1$. Updates: given $i,j,c$ increment $t_c$ between indices $i$ and $j$. After every update output $\sum_k \max{t_0[k],t_1[k]}$.
Deep Reinforcement Learning
Stable Baselines rely on TF 1.x but Stable Baselines v3 rely on PyTorch.
Organizing contests with judges
AlphaGo and Alpha Zero
In December 2016 we presented it at ENS ParisSaclay with Étienne Simon but apparently I never wrote a blog post in the end.
Six dates importantes en algorithmique
 300
 Algorithme d’Euclide (qui date peutêtre de l’école de Pythagore 530 av. J.C.)
Quadrangle Inequality trick for dynamic programs
Application: Given an ordered list of keys with frequencies, build a binary search tree on those keys which minimizes the average query cost.
Pareto optimality
Compute the pareto set of a given set of points in 2 or 3 dimensions.
Multiplying polynomials
You are given two polynomials $P$ and $Q$ and want to compute their product. The polynomials are given in form of an array with their coefficients.
Making pairs adjacent at minimal cost
You are given an array $X$ with the promise that each of its values appears exactly twice. You want to transform $X$ such that at the end all pairs are adjacent in the array. An allowed operation consists in removing a value from $X$ and appending it at the end. The cost of a solution is the maximal value which was moved.
Identifying the maximum in a sliding window
Given an array $x$ and an integer $k$, determine for every index $1 \leq j\leq n$ the maximum $x[i]$ among all indices $\max\{1,jk+1 \} \leq i \leq j$.
Maintaining sum of k largest items in a dynamic set
Maintain a set, allowing to add or remove elements and to query the sum of the up to k largest items.
Heap allowing to remove items
Maintain a set, allowing to add or remove elements and to query the smallest element.