Search Results

Documents authored by Pivoteau, Carine

Document
DOI: 10.4230/LIPIcs.ESA.2018.4
On the Worst-Case Complexity of TimSort

Authors: Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
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 slightly different versions of TimSort that are currently implemented in Python and in Java respectively. We propose a pedagogical and insightful proof that the Python version runs in O(n log n). The approach we use in the analysis also applies to the Java version, although not without very involved technical details. As a byproduct of our study, we uncover a bug in the Java implementation that can cause the sorting method to fail during the execution. We also give a proof that Python's TimSort running time is in O(n + n log rho), where rho is the number of runs (i.e. maximal monotonic sequences), which is quite a natural parameter here and part of the explanation for the good behavior of TimSort on partially sorted inputs.
Cite as

Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau. On the Worst-Case Complexity of TimSort. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.ESA.2018.4,
  author =	{Auger, Nicolas and Jug\'{e}, Vincent and Nicaud, Cyril and Pivoteau, Carine},
  title =	{{On the Worst-Case Complexity of TimSort}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.4},
  URN =		{urn:nbn:de:0030-drops-94678},
  doi =		{10.4230/LIPIcs.ESA.2018.4},
  annote =	{Keywords: Sorting algorithms, Merge sorting algorithms, TimSort, Analysis of algorithms}
}
Document
DOI: 10.4230/LIPIcs.CPM.2017.21
Gapped Pattern Statistics

Authors: Philippe Duchon, Cyril Nicaud, and Carine Pivoteau

Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Abstract
We give a probabilistic analysis of parameters related to alpha-gapped repeats and palindromes in random words, under both uniform and memoryless distributions (where letters have different probabilities, but are drawn independently). More precisely, we study the expected number of maximal alpha-gapped patterns, as well as the expected length of the longest alpha-gapped pattern in a random word.
Cite as

Philippe Duchon, Cyril Nicaud, and Carine Pivoteau. Gapped Pattern Statistics. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{duchon_et_al:LIPIcs.CPM.2017.21,
  author =	{Duchon, Philippe and Nicaud, Cyril and Pivoteau, Carine},
  title =	{{Gapped Pattern Statistics}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.21},
  URN =		{urn:nbn:de:0030-drops-73309},
  doi =		{10.4230/LIPIcs.CPM.2017.21},
  annote =	{Keywords: combinatorics on words, alpha-gapped repeats, random words, memoryless sources, analytic combinatorics}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.12
Good Predictions Are Worth a Few Comparisons

Authors: Nicolas Auger, Cyril Nicaud, and Carine Pivoteau

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
Most modern processors are heavily parallelized and use predictors to guess the outcome of conditional branches, in order to avoid costly stalls in their pipelines. We propose predictor-friendly versions of two classical algorithms: exponentiation by squaring and binary search in a sorted array. These variants result in less mispredictions on average, at the cost of an increased number of operations. These theoretical results are supported by experimentations that show that our algorithms perform significantly better than the standard ones, for primitive data types.
Cite as

Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. Good Predictions Are Worth a Few Comparisons. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.STACS.2016.12,
  author =	{Auger, Nicolas and Nicaud, Cyril and Pivoteau, Carine},
  title =	{{Good Predictions Are Worth a Few Comparisons}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.12},
  URN =		{urn:nbn:de:0030-drops-57135},
  doi =		{10.4230/LIPIcs.STACS.2016.12},
  annote =	{Keywords: branch misses, binary search, exponentiation by squaring, Markov chains}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.388
Average Analysis of Glushkov Automata under a BST-Like Model

Authors: Cyril Nicaud, Carine Pivoteau, and Benoît Razet

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract
We study the average number of transitions in Glushkov automata built from random regular expressions. This statistic highly depends on the probabilistic distribution set on the expressions. A recent work shows that, under the uniform distribution, regular expressions lead to automata with a linear number of transitions. However, uniform regular expressions are not necessarily a satisfying model. Therefore, we rather focus on an other model, inspired from random binary search trees (BST), which is widely used, in particular for testing. We establish that, in this case, the average number of transitions becomes quadratic according to the size of the regular expression.
Cite as

Cyril Nicaud, Carine Pivoteau, and Benoît Razet. Average Analysis of Glushkov Automata under a BST-Like Model. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 388-399, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{nicaud_et_al:LIPIcs.FSTTCS.2010.388,
  author =	{Nicaud, Cyril and Pivoteau, Carine and Razet, Beno\^{i}t},
  title =	{{Average Analysis of Glushkov Automata under a BST-Like Model}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{388--399},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.388},
  URN =		{urn:nbn:de:0030-drops-28809},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.388},
  annote =	{Keywords: Glushkov automata, random binary search tree, regular expression}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact