10 citations · 74 across the 27 of their papers we have counts for
5 papers · 1 filter
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
We present an average case analysis of a variant of dual-pivot quicksort. We show that the used algorithmic partitioning strategy is optimal, i.e., it minimizes the expected number…
The continuum Pólya-like random walk
Daniel Krenn, Hosam Mahmoud, Mark Daniel Ward
The Pólya urn scheme is a discrete-time process concerning the addition and removal of colored balls. There is a known embedding of it in continuous-time, called the Pólya process.…
An Extended Note on the Comparison-optimal Dual Pivot Quickselect
Daniel Krenn
In this note the precise minimum number of key comparisons any dual-pivot quickselect algorithm (without sampling) needs on average is determined. The result is in the form of exac…
Non-Minimality of the Width- Non-adjacent Form in Conjunction with Trace One -adic Digit Expansions and Koblitz Curves in Characteristic Two
Daniel Krenn, Volker Ziegler
This article deals with redundant digit expansions with an imaginary quadratic algebraic integer with trace as base and a minimal norm representatives digit set. For $w\geq…
Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
We present an average case analysis of two variants of dual-pivot quicksort, one with a non-algorithmic comparison-optimal partitioning strategy, the other with a closely related a…