12 Result(s)
within
Gianni Franceschini
-
Chapter and Conference Paper
Finding the Maximum Suffix with Fewer Comparisons
It is shown how to compute the lexicographically maximum suffix of a string of n ≥ 2 characters over a totally ordered alphabet using at most (4/3)n − 5/3 three-way character comparisons. The best previous bound,...
-
Article
Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves
We settle a long-standing open question, namely whether it is possible to sort a sequence of n elements stably (i.e., preserving the original relative order of the equal elements), using O(1) auxiliary space a...
-
Chapter and Conference Paper
In-Place Suffix Sorting
Given string T = T[1,...,n], the suffix sorting problem is to lexicographically sort the suffixes T[i,...,n] for all i. This problem is central to the construction of suffix arrays and trees with many application...
-
Chapter and Conference Paper
Radix Sorting with No Extra Space
It is well known that n integers in the range [1,n c ] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,
-
Article
Optimal Implicit Dictionaries over Unbounded Universes
An array of n distinct keys can be sorted for logarithmic searching or can be organized as a heap for logarithmic updating, but it is unclear how to attain logarithmic time for both searching and updat...
-
Chapter and Conference Paper
Sorting by Merging or Merging by Sorting?
In the comparison model the only operations allowed on input elements are comparisons and moves to empty cells of memory. We prove the existence of an algorithm that, for any set of s ≤n sorted sequences containi...
-
Chapter and Conference Paper
Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves
We settle a long-standing open question, namely whether it is possible to sort a sequence of n elements stably (i.e. preserving the original relative order of the equal elements), using O(1) auxiliary space and p...
-
Chapter and Conference Paper
Optimal In-place Sorting of Vectors and Records
We study the problem of determining the complexity of optimal comparison-based in-place sorting when the key length, k, is not a constant. We present the first algorithm for lexicographically sorting n keys in O(
-
Chapter and Conference Paper
Cache-Oblivious Comparison-Based Algorithms on Multisets
We study three comparison-based problems related to multisets in the cache-oblivious model: Duplicate elimination, multisorting and finding the most frequent element (the mode). We are interested in minimizing...
-
Chapter and Conference Paper
A General Technique for Managing Strings in Comparison-Driven Data Structures
This paper presents a general technique for optimally transforming any dynamic data structure \(\mathcal{D}\) that oper...
-
Chapter and Conference Paper
Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees
We close an open issue on dictionaries dating back to the sixthies. An array of n keys can be sorted so that searching takes O(log n) time. Alternatively, it can be organized as a heap so that inserting and delet...
-
Chapter and Conference Paper
Optimal Cache-Oblivious Implicit Dictionaries
We consider the issues of implicitness and cache-obliviousness in the classical dictionary problem for n distinct keys over an unbounded and ordered universe. One finding in this paper is that of closing the long...
