Searchability in merging and implicit data structures

We introduce the notion ofsearchability as a property of an in place merging algorithm. We show that a pair of sorted arrays can be merged in place in linear time, so that a search can be performed in logarithmic time at any point during the merging process. We apply this method to devise an implicit data structure which can support searches inO(log² n) time in the worst case, andO(logn) on the average, and insertions inO(logn) time, in the worst case.This research was partly supported by NSERC under grant A8237 and presented in preliminary form at the 10th International Colloquium on Automata, Languages and Programming.On leave from the University of Chile.     

On top-down splaying

The splay tree is a self-adjusting binary search tree which has a good amortized performance. This paper studies some properties of top-down splay trees. Different ways to charge for the primitive operations of top-down splaying are discussed. We also give some empirical results concerning the behaviour of different top-down restructuring algorithms.This work was supported by the Academy of Finland.     

On the Divergence of Polynomial Interpolation in the Complex Plane

We extend the results in [1] and [2] from the divergence of Hermite—Fejér interpolation in the complex plane to the divergence of arbitrary polynomial interpolation in the complex plane. In particular, we prove the following theorem: Let \D _n =-1≤ t ₁ ⁽ⁿ⁾ <⋅s<t _n ⁽ⁿ⁾ <1 . Let \v _k ⁽ⁿ⁾ be polynomials of arbitrary degree such that \v _k ⁽ⁿ⁾ (t _j ⁽ⁿ⁾ )=\d _kj . Then the Lebesgue function tends to infinity at every complex neighborhood of some point in [-1,1] . March 23, 2000. Date revised: September 28, 2000. Date accepted: October 10, 2000.     

Alternative methods for the reconstruction of trees from their traversals

It is well-known that given the inorder traversal of a binary tree's nodes, along with either one of its preorder or postorder traversals, the original binary tree can be reconstructed using a recursive algorithm. In this short note we provide a short, elegent, iterative solution to this classical problem.This research was done while the author held a Navy/ASEE Summer Faculty Research Associateship at the Naval Research Laboratory     

On Weyl structures

We characterize the relation between the geometrical properties of Weyl manifolds and the algebraic properties of the Weyl algebras (§1) and the deformation algebras associated to two conformal Weyl connections (§2). The last section is devoted to the study of the Weyl-Lyra algebras associated to a conformal Weyl connection and a conformal semisymmetric connection.     

Constructing a binary tree from its traversals

This paper shows that a binary tree can be constructed from its preorder and inorder traversals in linear time and space.     

Efficient algorithms for tree reconstruction

In this note, we show thatO(n logn) operations are sufficient to reconstruct an ordered binary tree given its inorder traversal and either its preorder or postorder traversal. An alternative linear representation allows reconstruction usingO(n) operations.     

Stable in situ sorting and minimum data movement

In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg^(k+1) n+kn) comparisons (lg^(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.Research supported by Natural Sciences and Engineering Research Council of Canada grant No.A-8237 and the Information Technology Research Centre of Ontario.Supported in part by a Research Initiation Grant from the Virginia Engineering Foundation.     

On Shellsort and the frobenius problem

A boundO(N ^1+1/k ) for the running time of Shellsort, withO(logN) passes, is proved very simply by application of a Frobenius basis withk elements.     

On the construction of weighted time-optimal B-trees

B-trees have been popular data structures since their definition. Their success is due to the fact that a B-tree containingn keys is balanced with a height ofO(logn). However, for a given set of elements and their access frequencies, one can construct many B-trees (possibly with different heights). The average access costs of these trees may vary significantly. An algorithm to construct a weighted time-optimal B-tree is presented. A weighted time-optimal B-tree is one in which the weighted access cost is minimized. A dynamic programming algorithm is used to construct a weighted time-optimal B-tree givenn elements and their weights. The algorithm runs in timeO(mn ³ logn) and has a storage requirement ofO(mn ² logn) wherem is the order of the B-tree andn is the number of keys.This research was supported in part by Texas Advanced Research Grant 1080 and NASA Grant NAG 5–739.     

On discrete time ergodic filters with wrong initial data

For a class of non-uniformly ergodic Markov chains (X _n ) satisfying exponential or polynomial beta-mixing, under observations (Y _n ) subject to an IID noise with a positive density, it is shown that wrong initial data is forgotten in the mean total variation topology, with a certain exponential or polynomial rate.     

Uniform structures in the beginning of the third millenium

It is the aim of the present survey article to discuss briefly results published by various researchers in the area of uniform structures over the past five years.     

In-trees and plane embeddings of outerplanar graphs

A notion of anin-tree is introduced. It is then used to characterize and count plane embeddings of outerplanar graphs. In-trees have also been applied in the study of independent vertex covers of faces in outerplanar graphs.This research was partially supported by the grant RP.I.09, from the Institute of Informatics, University of Warsaw. Hospitality of the Institute of Datalogy, University of Copenhagen where this research has been completed is gratefully acknowledged.     

Improved bounds for the expected behaviour of AVL trees

In this paper we improve previous bounds on expected measures of AVL trees by using fringe analysis. A new way of handling larger tree collections that are not closed is presented. An inherent difficulty posed by the transformations necessary to keep the AVL tree balanced makes its analysis difficult when using fringe analysis methods. We derive a technique to cope with this difficulty obtaining the exact solution for fringe parameters even when unknown probabilities are involved. We show that the probability of a rotation in an insertion is between 0.37 and 0.73 (and seems to be less than 0.56), that the fraction of balanced nodes is between 0.56 and 0.78, and that the expected number of comparisons in a search seems to be at most 12% more than in the complete balanced tree.The work of the first author was also supported by the Institute for Computer Research of the University of Waterloo, the second author by a Natural Sciences and Engineering Research Council of Canada Grant No. A-3353, and the third by a Brazilian Coordenação do Aperfeiçoamento de Pessoal de Nível Superior Contract No. 4799/77 and by the University of Waterloo.     

A note on the height of thekth element in a heap

De Graaf and Kosters have studied the expected height of thekth element in a heap. They conjecture that, for largek, this is asymptotic to log₂ k + 0.72 .... We show that the height of thekth element is related to the depth of insertion in a digital search tree, and use this relation to prove their conjecture.This research was supported by grant FONDECYT (Chile) 91-1252.     

Array theory and the nial programming language

The Nested Interactive Array Language Nial is based on a mathematical theory of hierarchical rectangular arrays known as array theory. This paper gives a brief introduction to array theory and Nial and then discusses the main characteristics of the Nial language, its current implementation and some of its applications.Dedicated to Peter Naur on the occasion of his 60th birthday.     

On Cayley-Transform Methods for the Discretization of Lie-Group Equations

In this paper we develop in a systematic manner the theory of time-stepping methods based on the Cayley transform. Such methods can be applied to discretize differential equations that evolve in some Lie groups, in particular in the orthogonal group and the symplectic group. Unlike many other Lie-group solvers, they do not require the evaluation of matrix exponentials. Similarly to the theory of Magnus expansions in [13], we identify terms in a Cayley expansion with rooted trees, which can be constructed recursively. Each such term is an integral over a polytope but all such integrals can be evaluated to high order by using special quadrature formulas similar to the construction in [13]. Truncated Cayley expansions (with exact integrals) need not be time-symmetric, hence the method does not display the usual advantages associated with time symmetry, e.g., even order of approximation. However, time symmetry (with its attendant benefits) is attained when exact integrals are replaced by certain quadrature formulas. March 7, 2000. Final version received: August 10, 2000. Online publication: January 2, 2001.