Author name cluster

Walter Cunto

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

TCS Journal 2003 Journal Article

Optimal binary search trees with costs depending on the access paths

Jayme L. Szwarcfiter
Gonzalo Navarro
Ricardo Baeza-Yates
Joísa de S. Oliveira
Walter Cunto
Nívio Ziviani

We describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees. The time and space complexities of both algorithms are O(n k+2) and O(n k+1), respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys which are paths of special kinds in binary search trees. Finally, using generating functions, we present an exact analysis of the number of steps performed by the algorithms.

Details DOI

I&C Journal 1991 Journal Article

Fringe analysis for Extquick: Anin situ distributive external sorting algorithm

Walter Cunto
Gasto´n H. Gonnet
J. Ian Munro
Patricio V. Poblete

A newin situ external sorting algorithm, to be calledExtquick, is developed and its time and space performance are analysed. It is shown that Extquick performs more efficiently than similarin situ sorting algorithms based on Quicksort that appear in the literature. Since the computational tree of Quicksort-like sorting algorithms is equivalent to a search tree, techniques that model the time complexity of such a structure are then used for the analysis of Extquick.

Details DOI

STOC Conference 1984 Conference Paper

Average Case Selection

Walter Cunto
J. Ian Munro

We consider problems such as selecting the k -th smallest of n numbers in as few comparisons as possible on average. n + k - 0(1) comparisons are proved to be necessary for this particular problem when k ≤ n /2. This shows a technique of Floyd and Rivest is essentially optimal. 7 n /4 = o(n) comparisons, on average, are shown to be necessary and sufficient to find the maximum and median of a set. An upper bound of 9 n /4 + o(n) and a lower bound of 2 n − o(n) are shown for the max-min-median problem.

Details