5 Result(s)
within
Gianni Franceschini
Algorithm Analysis and Problem Complexity
Data Structures
Discrete Mathematics in Computer Science
-
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
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
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
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,
-
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,...
