All posts by date

This summer, I was in Palermo where the Educational Data Mining, Learning at Scale & AI in Education conferences were held.

I presented Anav Agrawal’s RAG tool, which we use in our course.

Anav Agrawal, Jill-Jênn Vie. AlgoAce: Retrieval-Augmented Generation for Assistance in Competitive Programming. CSEDM 2025 - 9th Educational Data Mining in Computer Science Education Workshop, Jul 2025, Palermo, Italy. [paper] [code]

I’ll tell you about what some colleagues from Cornell University and Berkeley University presented because it’s truly impressive.

Cornell

The professor (Rene Kizilcec) has 270 students.
He uploads his PDFs to some website hita.ai developed by former students.
Students can ask questions anonymously (it sources the answers to the pages of the course slides or to specific points in a course video) and the professor sees the anonymous conversations (this part is the most valuable).
He has automatic analytics on the most frequently asked questions.
The (6k?) students have asked 64k questions on the platform (local LLM) in a few years.
The professor uses it to verify that students are actually reading the articles he assigns (students have to debate a question with an AI that has read the article).

He told the anecdote that his colleague noticed that 5 students were cheating and told them: “Wow, I’m really impressed by the richness of your reasoning, how about you come and discuss it in my office?” and then the students said “Nooo, sorry, we cheated.”

Berkeley

Narges Norouzi has 900-1700 students per cohort in their first CS1 course, required for all students in the computer science and engineering departments.
Students are allowed to use an autograder for their homework but not for graded labs or projects https://sp25.datastructur.es/policies/ see also, from a different u, https://eecs-autograder.github.io/autograder.io
They reuse the (1 million) code submissions from students over the previous (7) years to help students debug, see what types of hints are useful, which directly feeds into their (the professors’) research. They have 105,000 queries from 2,000 students from the 2023-2024 academic year to their local LLM.
They are not allowed to conduct randomized controlled trials; their ethics committee (IRB) prohibits it, due to the impactness of this course and its scale.
They show that students complete homework faster with AI (unsurprisingly) but not practical assignments faster (they even have some negative results on practical assignments).
They had two papers nominated for best paper at AIED 2025 (below), one of which uses the curriculum to automatically determine students’ progress in the course (knowledge tracing) and make appropriate recommendations.

Modeling Student Knowledge Progression in Intelligent Tutoring Interactions Abigail O’Neill, Kanav Mittal, Hanna Schlegel, Gireeja Ranade and Narges Norouzi https://drive.google.com/file/d/1As0EAEXOeyTnDqaMCOQqYY__BaN_d9gq/view?usp=sharing

Askademia: A Real-Time AI System for Automatic Responses to Student Questions Gaurav Tyagi, Meenakshi Mittal, Azalea Bailey, Gireeja Ranade and Narges Norouzi https://drive.google.com/file/d/1TOAuYZutWz8IWmWj_NLneL8atbUEcoVK/view?usp=drive_link

Update : Merci à Marc de Falco qui a trouvé une erreur dans le code initial. J’élabore là-dessus ci-dessous.

L’autre jour, en jury de l’agrégation d’informatique où j’ai eu la chance de participer de 2022 à 2025 en compagnie de collègues et candidats aussi brillants que passionnés, le candidat choisit la leçon sur la programmation dynamique et fait son développement sur le célèbre algorithme de sac à dos. Une collègue pose la question : “Qu’est-ce qui se passe si les capacités des poids sont négatives ?”

Cette question permet d’illustrer une différence entre mémoïsation et programmation dynamique.

On commence par la façon classique de résoudre le problème dans le cas des capacités positives $c_i \geqslant 0$. La relation de récurrence (équation de Bellman) est la suivante.

Si $maxval[i][c]$ est la capacité maximale que l’on peut atteindre avec les $i \geqslant 0$ premiers objets et une capacité limite de $c$, alors $maxval[0][c] = 0$ pour toute capacité $c$ (pas d’objet) et quand $i \geqslant 1$,

On peut faire un balayage avec une double boucle pour aller en nombre d’objets croissant et capacité croissante (bottom-up). Complexité temps et mémoire : $O(nC)$ où $n$ est le nombre d’objets et $C$ est la capacité du sac à dos.

capacities = [2, 3, 5]
values = [6, 4, 2]
cmax = 9

def knapsack():
    n = len(capacities)
    max_value = [[0] * (1 + cmax) for _ in range(n + 1)]
    candidates = []
    for i in range(1, n + 1):
        for c in range(0, cmax + 1):
            candidates = [max_value[i - 1][c]]
            if c >= capacities[i - 1]:
                candidates.append(values[i - 1] + max_value[i - 1][c - capacities[i - 1]])
            max_value[i][c] = max(candidates)
    return max_value[n][cmax]

knapsack()

Run

En effet, on peut obtenir une valeur de 10 avec les 2 premiers objets (capacité totale 2 + 3 = 5 en dessous de la limite 9).

Cette méthode nous permet de répondre à toutes les questions possibles : que vaut $maxval$ pour les $i$ premiers objets et une capacité limite $c$ ? On visite tous les états possibles $(i, c)$.

Regardons à présent à quoi ressemblerait une solution qui mémoïserait (i.e. stockerait les appels récursifs pour ne pas recalculer la même quantité plusieurs fois). On peut s’appuyer sur l’astuce Python du décorateur @cache. (On est plusieurs profs à penser que la mémoïsation devrait être enseignée avant la programmation dynamique.) Notez au passage à quel point ce code est similaire au précédent. En particulier, si on faisait du Haskell, on n’aurait pas besoin du décorateur.

from functools import cache

capacities = [2, 3, 5]
values = [6, 4, 2]
cmax = 9

@cache
def max_value(i, c):
    candidates = []
    if i == 0:
        return 0
    candidates.append(max_value(i - 1, c))
    if c >= capacities[i - 1]:
        candidates.append(values[i - 1] + max_value(i - 1, c - capacities[i - 1]))
    return max(candidates)

n = len(capacities)
max_value(n, cmax)

Run

Complexité : autant d’appels que strictement nécessaire, $O(nC)$ au pire. Mais soyons plus précis.

Soit $C_M$ le nombre d’états uniques (cases mémoire) parcourus par l’algorithme. On a d’une part $C_M \leq (n + 1)(C + 1)$ car c’est le nombre total d’états possibles, et d’autre part $C_M \leq 2^n$ car c’est le nombre total de combinaisons possibles (et d’appels récursifs si on ne faisait pas de mémoïsation).

On voit bien que selon le régime, par exemple si $n$ est petit et $C$ grand, il vaut mieux tout tester, même avec l’algorithme naïf, plutôt que de remplir tous les états possibles. Si $C$ est petit on a plutôt envie d’exploiter la redondance. Dans tous les cas, l’algorithme de mémoïsation est optimal en temps (mais pas en mémoire). Le gain par rapport au naïf est $C_M / 2^n$ et par rapport à l’algo de programmation dynamique est $C_M / ((n + 1)(C + 1))$. Faudrait que je fasse un dessin sur une instance avec les cases visitées pour chaque algorithme.

À présent, regardons ce qui se passe dans le cas de capacités négatives. (Veillez à bien exécuter les cellules précédentes avant celle-ci.)

La mémoïsation fonctionne et reste optimale. Update : en fait non, le code ci-dessus est faux. Cherchez un contre-exemple, en voici un.

capacities = [2, -1]
values = [1, 1]
cmax = 1

n = len(capacities)
max_value.cache_clear()  # Sinon les appels sont encore dans la mémoire
max_value(n, cmax)

Run

Ici, la réponse est bonne : 2, on prend tous les objets. Mais si on met les objets dans l’autre ordre :

capacities = [-1, 2]
values = [1, 1]
cmax = 1

n = len(capacities)
max_value.cache_clear()
max_value(n, cmax)

Run

On rate l’objet de poids 2 car on ne s’autorise pas à passer par des états de capacités négatives qu’on pourrait rattraper plus tard. Autorisons donc les capacités négatives tant que l’état final convient. La relation de récurrence est donc :

Code modifié :

from functools import cache

capacities = [-1, 2]
values = [1, 1]
cmax = 1

@cache
def max_value_neg(i, c):
    candidates = []
    if i == 0:
        return 0 if c >= 0 else float('-inf')  # Valeur admissible s'il reste de la capacité
    return max(
        max_value_neg(i - 1, c),
        values[i - 1] + max_value_neg(i - 1, c - capacities[i - 1])
    )

n = len(capacities)
max_value_neg(n, cmax)

Run

Quelle est sa complexité ? On pourrait l’améliorer en éliminant les branches non prometteuses (s’il ne reste plus d’objets pour aboutir à un état positif). Qu’en est-il de l’algorithme itératif de programmation dynamique au début de ce billet ?

capacities = [-1, 2]
values = [1, 1]
cmax = 1

knapsack()

Run

Exercice au lecteur : comment modifier le code précédent de knapsack pour qu’il fonctionne dans le cas de capacités négatives ? Quel est le nombre d’états maximaux à considérer ? Quelle est la structure de données adaptée ? Faites un dessin sur papier pour voir ce qui se passe.

Une autre solution d’un étudiant est de partir d’un état où on a pris toutes les capacités négatives et considérer des actions “enlever l’objet” afin de se ramener au sac à dos à capacités positives. C’est également une solution correcte.

Méta : si ça vous intéresse de voir comment j’ai chargé pyodide sur ce blog post Jekyll, vous pouvez regarder en bas du source de cette page. Vous pouvez faire une PR pour remplacer le premier bloc par un textarea (avec coloration syntaxique svp) pour modifier le code.

En musique, on change d’octave en doublant la fréquence. On passe à la quinte en multipliant par 3/2.

If we want to find the longest (strictly) increasing subsequence of an array $a$ of size $n$, of course we can assume that $dp[i]$ is the answer for the first $i$ elements and then, as a LIS of size $n$ contains a LIS of size $n - 1$:

This gives a first algorithm in $O(n^2)$. Can we do better?

• We do not need to remember all LIS of size $\ell$. We just need to remember the smallest end for a LIS of size $\ell$, called $t[\ell]$.
• The list of smallest ends happens to be increasing (but not necessarily a subsequence). Each $t[\ell]$ forces $t[\ell - 1]$ to be lower.

In this case, we can binary search for the opt LIS to which we can add one element. This gives $O(n \log n)$. I think this is an example of Divide and Conquer DP.

I was wondering what was the $O(n \log n)$ that relies on a segment tree. A blog post on Codeforces had the answer (of course!). We need to define a new dp:
$dp[i, v]$ is the LIS using first $i$ elements finishing in $v$. Then we just need to do a min query over $dp[i, 1:v - 1]$.

(A notebook is on the way.)

Étant donnée une liste de chaînes de caractères L, construire une structure de données qui permet en temps linéaire d’identifier toutes les occurrences des mots de L à l’intérieur d’un mot S donné.

Back in the good ol’ agrégation days, I remember I used as développement¹ a nice 2-approx algorithm for the traveling salesman problem where the weights on the edges are given by the Euclidean distance between nodes.

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.

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.

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.

You are given an histogram and want to identify the area of the largest rectangle that fits under the histogram.

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 a tree with paths or caterpillars.

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.

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]}$.

Stable Baselines rely on TF 1.x but Stable Baselines v3 rely on PyTorch.

SPOJ

In December 2016 we presented it at ENS Paris-Saclay with Étienne Simon but apparently I never wrote a blog post in the end.

-300

Algorithme d’Euclide (qui date peut-être de l’école de Pythagore 530 av. J.C.)

Application: Given an ordered list of keys with frequencies, build a binary search tree on those keys which minimizes the average query cost.

Compute the pareto set of a given set of points in 2 or 3 dimensions.