# 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éveloppement1 a nice 2-approx algorithm for the traveling salesman problem where the weights on the edges are given by the Euclidean distance between nodes.

1. This must mean nothing to non-French 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,n-1\}$ the elements of the permutations on $\{0,1,\ldots,n-1\}$ 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 meta-analyses 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.

## AlphaGo and Alpha Zero

In December 2016 we presented it at ENS Paris-Saclay 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,j-k+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.