3 citations · 4 across the 5 of their papers we have counts for
7 papers
Leap generators for composition schemes
Éric Fusy, Carine Pivoteau
Leap generators have been introduced in [Duchon et al.'04] for exact-size random generation of structures in a class of the form (sequence c…
Effective Asymptotics of Combinatorial Systems
Carine Pivoteau, Bruno Salvy
Analytic combinatorics studies asymptotic properties of families of combinatorial objects using complex analysis on their generating functions. In their reference book on the subje…
Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms
Cyril Nicaud, Carine Pivoteau, Stéphane Vialette
We analyze the classical Morris-Pratt and Knuth-Morris-Pratt pattern matching algorithms through the lens of computer architecture, investigating the impact of incorporating a simp…
Record-biased permutations and their permuton limit
Mathilde Bouvel, Cyril Nicaud, Carine Pivoteau
In this article, we study a non-uniform distribution on permutations biased by their number of records that we call \emph{record-biased permutations}. We give several generative pr…
On the Worst-Case Complexity of TimSort
Nicolas Auger, Vincent Jugé, Cyril Nicaud +1
TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. In fact, there are two…
Analysis of Algorithms for Permutations Biased by Their Number of Records
Nicolas Auger, Mathilde Bouvel, Cyril Nicaud +1
The topic of the article is the parametric study of the complexity of algorithms on arrays of pairwise distinct integers. We introduce a model that takes into account the non-unifo…