Narrow Results

We develop a new class of weight balanced binary search trees called β-balanced binary search trees (β-BBSTs). β-BBSTs are designed to have reduced internal path length. As a result, they are expected to exhibit good search time characteristics. Individual search, insert, and delete operations in an n node β-BBST take O(log n) time for . Experimental results comparing the performance of β-BBSTs, WB(α) trees, AVL-trees, red/black trees, treaps, deterministic skip lists and skip lists are presented. Two simplified versions of, β-BBSTs are also developed.

A new priority queue is introduced, for which the cost to insert a new item is constant and the cost to delete the item x with the minimum value is O(log k_x), where k_x, is the number of items that are inserted after x and are still in the heap when x is deleted. We achieve the above bounds in both the amortized case and the worst case.

This paper describes a random model for chemical graphs that captures the notion of valence along with algorithms to generate chemical graphs using this model. An approach for computing the probability that a particular chemical graph is generated under this model is provided. The model is also used to provide theoretical bounds on the accuracy of a class of canonical labeling algorithms for a class of hydrocarbons.

In this paper we present a strategy to maintain a dynamic optimal binary search tree. The algorithms for insertion and deletion use swapping as the basic operation. Since in average situations the tree reorganization is limited to local changes, it can be favourably compared with the local balancing algorithms. The present algorithms dynamically maintain the optimal tree with an amortized time of O(log₂ n), where n is the total number of nodes in the tree. In the worst case situations, the algorithms take only O(n) time. This is significant when they are compared to the algorithms producing static optimal binary search trees.

The performance of hash tables is analyzed in a parallel context. Assuming that a hash table of fixed size is allocated in the shared memory of a PRAM with n processors, a Ph-step is defined as a PRAM computation in which each processor searches or inserts a key in the table. It is shown that the maximum number of table probes needed for a single key in a Ph-step is Ω(log_1/αⁿ) and O(log_1/α′ⁿ) with high probability, where α and α′ are the load factors before and after the execution of the Ph-step. However, a clever implementation of a Ph-step is proposed, which runs in time O((log_1/α′n)^1/2) with high probability. The algorithm exploits the fact that operations relative to different keys have different durations; hence, the processors in charge of shorter operations, once finished, are used to perform part of the longer ones.

We consider heap-ordered trees in this paper. The main theorems in this paper show that the average and the variance of the altitude (or level) of the nodes in a random n-node heap-ordered tree are and , respectively where γ=0.5772156649… is the Euler’s constant.

A simple algorithm is given to rebalance a binary search tree of optimal height after a single update. The algorithm uses time which is linear in the number of nodes. In comparison to previous algorithms it is short and very easy to implement. Moreover, this algorithm can be used to implement other classes of balanced trees and it is suitable for each update. When applied to perfectly balanced trees it has a lower average cost than previous algorithms.

There is a growing need for expertise both in image analysis and in software engineering. To date, these two areas have been taught separately in an undergraduate computer and information science curriculum. However, we have found that introduction to image analysis can be easily integrated in data-structure courses without detracting from the original goal of teaching data structures. Some of the image processing tasks offer a natural way to introduce basic data structures such as arrays, queues, stacks, trees and hash tables. Not only does this integrated strategy expose the students to image related manipulations at an early stage of the curriculum but it also imparts cohesiveness to the data-structure assignments and brings them closer to real life. In this paper we present a set of programming assignments that integrates undergraduate data-structure education with image processing tasks. These assignments can be incorporated in existing data-structure courses with low time and software overheads. We have used these assignment sets thrice: once in a 10-week duration data-structure course at the University of California, Santa Barbara and the other two times in 15-week duration courses at the University of South Florida, Tampa.

Our new algorithm and data structure, pyramid search (PS) and skip ring, were created with the help of circular linked list and skip list algorithms and data structures. In circular linked list, operations were performed on a single circular list. Our new data structure consists of circular linked lists formed in layers which were linked in a pyramid way. Time complexity of searching, insertion and deletion algorithms equal to $O$ (lg$N$) in an $N$-element skip ring data structure. Therefore, skip ring data structure is employed more effectively ($O$(lg$N$)) in circumstances where circular linked lists ($O(N)$) are used. The priority is determined based on the searching frequency in PS which was developed in this study. Thus, the time complexity of searching is almost $\mathrm{\Theta }$(1) for $N$ records data set. In this paper, the applications of searching algorithms like linear search (LS), binary search (BS) and PS were realized and the obtained results were compared. The obtained results demonstrated that the PS algorithm is superior to the BS algorithm.

We present a model of the data structure domain that is expressed in terms of the GenVoca domain modeling concepts [7]. We show how familiar data structures can be encapsulated as realms of plug-compatible, symmetric, and reusable components, and we show how complex data structures can be formed from their composition. The target application of our research is a precompiler for specifying and generating customized data structures.

In this paper we present a linear space dynamic data structure for two-dimensional orthogonal range reporting and emptiness queries. This data structure answers range reporting queries in time for any ε > 0 and k the size of the answer. Our data structure also supports emptiness and one-reporting queries in time O(log n log log n). The model of computation used in this paper is a unit-cost RAM model.

We study the aggregate/group top-k nearest neighbor searching for the Max operator in the plane, where the distances are measured by the L₁ metric. Let P be a set of n points in the plane. Given a query set Q of m points, for each point p ∈ P, the aggregate-max distance from p to Q is defined to be the maximum distance from p to all points in Q. Given Q and an integer k with 1 ≤ k ≤ n, the query asks for the k points of P that have the smallest aggregate-max distances to Q. We build a data structure of O(n) size in O(n log n) time, such that each query can be answered in O(m+k log n) time and the k points are reported in sorted order by their aggregate-max distances to Q. Alternatively, we build a data structure of O(n log n) size in O(n log² n) time that can answer each query in O(m + k + log³ n) time.

In this paper, we investigate the problem of finding the common tangents of two convex polygons that intersect in two (unknown) points. First, we give a Θ(log²n) bound for algorithms that store the polygons in independent arrays. Second, we show how to beat the lower bound if the vertices of the convex polygons are drawn from a fixed set of n points. We introduce a data structure called a compact interval tree that supports common tangent computations, as well as the standard binary-search-based queries, in O(logn) time apiece. Third, we apply compact interval trees to solve the subpath hull query problem: given a simple path, preprocess it so that we can find the convex hull of a query subpath quickly. With O(nlogn) preprocessing, we can assemble a compact interval tree that represents the convex hull of a query subpath in O(logn) time. In order to represent arrangements of Lines implicitly, Edelsbrunner et al. used a less efficient structure, called bridge trees, to solve the subpath hull query problem. Our compact interval trees improve their results by a factor of O(logn). Thus, the present paper replaces the paper on bridge trees referred to by Edelsbrunner et al.

In this paper we present the Brep-index, a multidimensional space partitioning data structure that provides quick spatial access to the vertices, edges and faces of a boundary representation (Brep), thus yielding a single unified representation for polyhedral solids. We give an algorithm for the construction of the Brep-index and prove its correctness. We show that its size is Ω(v+e+f), where v, e, and f are the number of vertices, edges, and faces of the Brep. The lower bound can be achieved for some Breps by compressing the structure using simple rewrite rules. We then demonstrate robust point and line/Brep classification methods given an implementation that uses finite-precision arithmetic.

A new class of geometric intersection searching problems is introduced, which generalizes previously-considered intersection searching problems and is rich in applications. In a standard intersection searching problem, a set S of n geometric objects is to be preprocessed so that the objects that are intersected by a query object q can be reported efficiently. In a generalized problem, the objects in S come aggregated in disjoint groups and what is of interest are the groups, not the objects, that are intersected by q. Although this problem can be solved easily by using an algorithm for the standard problem, the query time can be Ω(n) even though the output size is just O(1). In this paper, algorithms with efficient, output-size-sensitive query times are presented for the generalized versions of a number of intersection searching problems, including: interval intersection searching, orthogonal segment intersection searching, orthogonal range searching, point enclosure searching, rectangle intersection searching, and segment intersection searching. In addition, the algorithms are also space-efficient.

Power circuits are data structures which support efficient algorithms for highly compressed integers. Using this new data structure it has been shown recently by Myasnikov, Ushakov and Won that the Word Problem of the one-relator Baumslag group is in P. Before that the best known upper bound was non-elementary. In the present paper we provide new results for power circuits and we give new applications in algorithmic algebra and algorithmic group theory: (1) We define a modified reduction procedure on power circuits which runs in quadratic time, thereby improving the known cubic time complexity. The improvement is crucial for our other results. (2) We improve the complexity of the Word Problem for the Baumslag group to cubic time, thereby providing the first practical algorithm for that problem. (The algorithm has been implemented and is available in the CRAG library.) (3) The main result is that the Word Problem of Higman's group is decidable in polynomial time. The situation for Higman's group is more complicated than for the Baumslag group and forced us to advance the theory of power circuits.

In this paper we describe a realization of the Wavelet Element Method (WEM), for numerically solving second-order elliptic PDEs on fairly general domains. We describe in a detailed form the construction of biorthogonal wavelet bases on these domains. The domain of interest is split into subdomains and mapped to the unit reference cube. The bases obtained on each subdomain are matched to obtain continuous global wavelet bases. Suitable data structures for an efficient implementation of the wavelet Galerkin method are described.

In this paper we present two algorithms for building lexicons in Directed Acyclic Word-Graphs (DAWGs). The two algorithms, one for deterministic and the other for non-deterministic DAWGs, can be used instead of the traditional subset construction method. Although the proposed algorithms do not produce the optimal DAWG (i.e., the one with the minimum number of states), they are simple, fast and able to build the DAWG incrementally, as new words are added to the lexicon. Thus, building large lexicons in a DAWG structure becomes an easy task, even for a modest computer.

The notion of entanglement is the most well-known nonclassical correlation in quantum mechanics, and a fundamental resource in quantum information and computation. This correlation, which is displayed by certain classes of quantum states, is of utmost importance when dealing with protocols, such as quantum teleportation, cryptography and quantum key distribution. In this paper, we exploit a classification of tripartite entanglement by introducing the concepts of entangled hypergraph and evolving entangled hypergraph as data structures suitable to model quantum protocols which use entanglement. Finally, we present a few examples to provide applications of this model.

We give a priority queue that achieves the same amortized bounds as Fibonacci heaps. Namely, find-min requires O(1) worst-case time, insert, meld and decrease-key require O(1) amortized time, and delete-min requires O(log n) amortized time. Our structure is simple and promises an efficient practical behavior when compared to other known Fibonacci-like heaps. The main idea behind our construction is to propagate rank updates instead of performing cascaded cuts following a decrease-key operation, allowing for a relaxed structure.