Advanced Algorithmics

ENS Paris-Saclay · 2026–2027

Approximation and String Algorithms

Lectures
Thomas Nowak · Mondays 8:30–10:30, room 1O07
Problem sessions
Mihaela Sighireanu · Mondays 10:45–12:45, room 1O07
Lecture notes
PDF · updated as the course progresses
Date Session Topic
Sep 7 Lecture 1 Vertex cover, set cover, subset sum
Sep 7 Lecture 2 Metric TSP, knapsack, load balancing
Sep 14 Lecture 3 Linear programming, MAX-CUT
Sep 14 Problem session 1 Greedy approximation
Sep 21 Lecture 4 k-center, local search
Sep 21 Problem session 2 TSP, knapsack, scheduling
Sep 28 Lecture 5 Morris–Pratt, Knuth–Morris–Pratt
Sep 28 Problem session 3 LP relaxations and rounding
Oct 5 Lecture 6 Simon's algorithm, Boyer–Moore
Oct 5 Problem session 4 k-center and local search
Oct 12 Problem session 5 Borders, periods, Fine–Wilf
Oct 12 Problem session 6 String-matching automata, Boyer–Moore
Oct 19 Lecture 7 Two-way string matching
Oct 19 Problem session 7 Critical factorizations, two-way matching
Nov 2 Final exam

Distributed and Online Algorithms

Lectures
Thomas Nowak · Mondays 8:30–10:30, room 1O07
Problem sessions
Mondays 10:45–12:45, room 1O07
Lecture notes
PDF · updated as the course progresses
Date Session Topic
Jan 18 Lecture 1 Quicksort, secretary problem, online paging
Jan 18 Problem session 1 Ski rental, paging, secretary variants
Jan 25 Lecture 2 Skip lists, universal hashing
Jan 25 Problem session 2 Universal hashing, skip lists, Rabin–Karp
Feb 1 Lecture 3 Chernoff bounds, balls into bins
Feb 1 Problem session 3 Probabilistic method, coupon collector
Feb 8 Lecture 4 Synchronous message passing, BFS, coloring
Feb 8 Problem session 4 Synchronous model, BFS, Cole–Vishkin
Feb 22 Lecture 5 Symmetry breaking, Luby's MIS
Feb 22 Problem session 5 MIS and coloring, leader election in rings
Mar 1 Lecture 6 Asynchrony, faults, FLP impossibility
Mar 1 Problem session 6 Asynchronous BFS, bivalence arguments
Mar 8 Lecture 7 Approximate, randomized, Byzantine consensus
Mar 8 Problem session 7 Consensus rates and resilience bounds
Mar 15 Final exam