Dichotomic Selection on Words: A Probabilistic Analysis

DOI10.4230/LIPICS.CPM.2019.19MaRDI QIDQ5088910zbMATH OpenOpenAlexFDO

Authors Ali Akhavi, Julien Clément, Dimitri Darthenay, 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 algorithmsaverage case analysis of algorithmsdichotomic selectioninformation theorylcp-arraysuffix arraytext algorithmstrie

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Self-alignments in words and their applications
• Towards a realistic analysis of the QuickSelect algorithm
• A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms
• An estimate of mean efficiency of search trees for arbitrary sets of binary words
• A probabilistic analysis of the Floyd–Rivest expected time selection algorithm

Cites work

• A probabilistic analysis of the height of tries and of the complexity of triesort
• Algorithm Theory - SWAT 2004
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Dynamical sources in information theory: A general analysis of trie structures
• Dynamical sources in information theory: Fundamental intervals and word prefixes
• Entropy quotients and correct digits in number-theoretic expansions
• Equipartition of interval partitions and an application to number theory
• scientific article; zbMATH DE number 108390 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 194543 (Why is no real title available?)
• Inducing the LCP-array
• Permuted Longest-Common-Prefix Array
• Suffix Arrays: A New Method for On-Line String Searches
• The depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Tight bounds for searching a sorted array of strings
• Towards a realistic analysis of some popular sorting algorithms
• Towards a realistic analysis of the QuickSelect algorithm

Cited in

(1)

• Lochs-type theorems beyond positive entropy

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088910)