Dichotomic Selection on Words: A Probabilistic Analysis

DOI10.4230/LIPIcs.CPM.2019.19OpenAlexW2954950410MaRDI QIDQ5088910

Julien Clément, Dimitri Darthenay, Ali Akhavi, Loïck Lhote, Brigitte Vallée

Publication date: 18 July 2022

Full work available at URL: https://hal.archives-ouvertes.fr/hal-02152162

zbMATH Keywords

analysis of algorithmsinformation theorysuffix arraytrietext algorithmsaverage case analysis of algorithmsdichotomic selectionlcp-array

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (1)

Lochs-type theorems beyond positive entropy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards a realistic analysis of the QuickSelect algorithm
• A probabilistic analysis of the height of tries and of the complexity of triesort
• Dynamical sources in information theory: Fundamental intervals and word prefixes
• Dynamical sources in information theory: A general analysis of trie structures
• Tight Bounds for Searching a Sorted Array of Strings
• Equipartition of interval partitions and an application to number theory
• Suffix Arrays: A New Method for On-Line String Searches
• Permuted Longest-Common-Prefix Array
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Algorithms on Strings, Trees and Sequences
• The Depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace
• Inducing the LCP-Array
• Entropy quotients and correct digits in number-theoretic expansions
• Algorithm Theory - SWAT 2004
• Towards a Realistic Analysis of Some Popular Sorting Algorithms
• Algorithms on Strings

This page was built for publication: Dichotomic Selection on Words: A Probabilistic Analysis