We describe a precompression algorithm that effectively represents any long common strings that appear in a file. The algorithm interacts well with standard compression algorithms that represent shorter strings that are near in the input text. Our experiments show that some real data sets do indeed contain many long common strings. We extend the fingerprint mechanisms of our algorithm to a program that identifies long common strings in an input file. This program gives interesting insights into the structure of real data files that contain long common strings.

Abstract We recount the history of a new qsortfunction for a C library. Our function is clearer, faster and more robust than existing sorts. It chooses partitioning elements by a new sampling scheme; it partitions by a novel solution to Dijkstra's Dutch National Flag problem; and it swaps efficiently. Its behavior was assessed with timing and debugging testbeds, and with a program to certify performance. The design techniques apply in domains beyond sorting.

This paper describes a set of interfaces for numerical subroutines. Typing a short (often one-line) description allows one to solve problems in application domains including least-squares data fitting, differential equations, minimization, root finding, and integration. Our approach of “template-driven programming” makes it easy to build such an interface: a simple one takes a few hours to construct, while a few days suffice to build the most complex program we describe.

This paper describes efficient algorithms for computing approximate traveling salesman tours in multidimensional point sets. We describe implementations of a dozen starting heuristics (including Nearest Neighbor and Farthest Insertion) and three local optimizations (including 2-Opt and 3-Opt). Experiments indicate that most of the algorithms run in O(N log N) time on uniform data sets, and many run almost as fast on very nonuniform data. The program that implements the algorithms is able to solve uniform planar million-city traveling salesman problems to within a few percent of optimal in several midicomputer CPU hours. The algorithms and program apply to many distance metrics and dimensions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A K-d tree represents a set of N points in K-dimensional space. Operations on a semidynamic tree may delete and undelete points, but may not insert new points. This paper shows that several operations that require Ο(log N) expected time in general K-d trees may be performed in constant expected time in semidynamic trees. These operations include deletion, undeletion, nearest neighbor searching, and fixed-radius near neighbor searching (the running times of the first two are proved, while the last two are supported by experiments and heuristic arguments). Other new techniques can also be applied to general K-d trees: simple sampling reduces the time to build a tree from Ο(KN log N) to Ο(KN + N log N), and more advanced sampling builds a robust tree in the same time. The methods are straightforward to implement, and lead to a data structure that is significantly faster and less vulnerable to pathological inputs than ordinary K-d trees.

Typical software engineering courses teach principles in lectures and readings, then apply them in the development of a single program (requiring several months). We recently taught a software engineering class that incorporated many smaller exercises (requiring several hours). The class was successful: students were able to experiment with a broad set of ideas, and make interesting mistakes without jeopardizing the grades of their development team. This paper describes some tools and techniques we taught, and suggests how they might be incorporated into typical software engineering classes.

We study the asymptotic expected behavior of the First Fit and First Fit Decreasing bin packing algorithms applied to items chosen uniformly from the interval (0,u], u ≤ 1. Our results indicate that the algorithms perform even better than previously expected.

Three techniques in computational geometry are explored: Scaling solves a problem by viewing it at increasing levels of numerical precision; activation is a restricted type of update operation, useful in sweep algorithms; the Cartesian tree is a data structure for problems involving maximums and minimums. These techniques solve the minimum spanning tree problem in Rk1 and Rk@@@@ in O(n(lg n)rlg lg n) time and O(n) space, where for Rk@@@@ and k ≥ 3, r = k-2; for Rk1, r = 1, 2, 4 for k = 3, 4, 5 and r = k for k > 5. Other problems solved include Rk1and Rk all nearest neighbors, post office and maximum spanning tree; Rk maxima, Rk rectangle searching problems, and Zkp all nearest neighbors (1 ≤ p ≤ @@@@).

In this paper we study a class of resource tradeoffs that arise in such problems as parallel sorting algorithms, linear recursion schemata, VLSI layouts, and searching problems. The tradeoffs can all be traced to the common structure of a multiway tree, and the special class of binomial trees (which are isomorphic to the binomial coefficients) correspond to particularly efficient algorithms. Although all of the tradeoffs that we exhibit are upper bounds, we present evidence to show that the approach can also lead to lower bounds.

In this paper we investigate the problem of reporting all intersecting pairs in a set of n rectilinearly oriented rectangles in the plane. This problem arises in applications such as design rule checking of very large-scale integrated (VLSI) circuits and architectural databases. We describe an algorithm that solves this problem in worst case time proportional to n lg n + k, where k is the number of interesecting pairs found. This algorithm is optimal to within a constant factor. As an intermediate step of this algorithm, we solve a problem related to the range searching problem that arises in database applications. Although the algorithms that we describe are primarily theoretical devices (being very difficult to code), they suggest other algorithms that are quite practical.

RandomThe empirical testing of a program often calls for generating a set of random numbers and then nnmedmtely sorting them.In this paper we consider the problem of accomplishing that process in a single step.generating a sorted list of random numbers (specifically, reals chosen uniformly from [0, 1]).The method we describe generates the randoms in linear worst-case time, is perfectly random (if it can call a perfectly random generator for a single uniform), and can be described in just a few lines of Algol or Pascal code.If the numbers are not requtred to be generated all at once {but are rather to be used one at a time), then the method can be implemented as a subroutine to produce the "next" number m constant tnne and requires only constant storage Key Words and Phrases: random number generation, sorting, probabilistic methods in algorithm design, linear-time algorithms CR Categories: 5.25, 5.

Geometric closest potnt problems deal with the proxLmity relationships in k-dimensional point sets.Examples of closest point problems include building minimum spanning trees, nearest neighbor searching, and triangulation constructmn Shamos and Hoey [17] have shown how the Voronoi dtagram can be used to solve a number of planar closest point problems in optimal worst case tune.In this paper we extend thmr work by giving optimal expected.trinealgorithms for solving a number of closest point problems in k-space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimum spanning trees.In addition to establishing theoretical bounds, the algorithms in this paper can be implemented to solve practical problems very efficiently.

In this paper we study the problem of designing and specifying standard program components applicable to a wide variety of tasks; we choose for this study the specific problem domain of data structures for general searching problems. Within this domain Bentley and Saxe [1] have developed transformations for converting solutions of simple searching problems to solutions of more complex problems. We discuss one of those transformations, specify precisely the transformation and its conditions of applicability, and prove its correctness; we accomplish this by casting it in terms of abstract data types–specifically by using the Alphard form mechanism. The costs of the structures derived by this transformation are only slightly greater than the costs of the original structures, and the correctness of the transformation definition together with the correctness of the original structure assure the correctness of the derived structure. The transformation we describe has already been used to develop a number of new algorithms, and it represents a new level of generality in software engineering tools.

In this paper we will investigate transformations that serve as tools in the design of new data structures. Specifically, we study general methods for converting static structures (in which all elements are known before any searches are performed) to dynamic structures (in which the insertion of a new element can be mixed with searches). We will see three classes of such transformations (each based on a different counting scheme for representing the integers) and then use a combinatorial model to show the optimality of many of the transformations. Issues such as online data structures and deletion of elements are also examined. To demonstrate the applicability of these tools, we will study six new data structures that have been developed by applying the transformations.

Abstract If a reliable, high quality numerical algorithms library is to be developed then it is essential that we recognize the need for collaboration between different technical communities in the development of the library. This paper suggests an ultimate design for the library and describes the implications of that design for the people involved in the development of the library.

An interesting class of "geometric intersection problems" calls for dealing with the pairwise intersections among a set of N objects in the plane, These problems arise in many applications such as printed circuit design, architectural data bases, and computer graphics. Shamos and Hoey have described a number of algorithms for detecting whether any two objects in a planar set intersect. In this paper we extend their work by giving algorithms that count the number of such intersections and algorithms that report all such intersections.

The multidimensional binary search tree (abbreviated k-d tree) is a data structure for storing multikey records. This structure has been used to solve a number of "geometric" problems in statistics and data analysis. The purposes of this paper are to cast k-d trees in a database framework, to collect the results on k-d trees that have appeared since the structure was introduced, and to show how the basic data structure can be modified to facilitate implementation in large (and very large) databases.

A maximal vector of a set ~s one which is not less than any other vector m all components We derive a recurrence relation for computing the average number of maxunal vectors m a set of n vectors m d-space under the assumpUon that all (nl) a relative ordermgs are equally probable.Solving the recurrence shows that the average number of maxmaa is O((ln n) a-~) for fixed d We use this result to construct an algorithm for finding all the maxima that have expected running tmae hnear m n (for sets of vectors drawn under our assumptions) We then use the result to find an upper bound on the expected number of convex hull points m a random point set KE~ WORDS AND eHRASES maxtma of a set of vectors, average number of maxtma, expected-tsme algorithms, analysts of algorithms, convex hulls, dynamtc programming CR CATEGORIES" 5 25, 5.39, 5.42 Permtsston to copy without fee all or part of this material ts granted provtded that the copies are not made or distributed for direct commercial advantage, the ACM copyrtght notice and the tRle of the pubhcatlon and its date appear, and notice ts gtven that copying ts by permission of the Assoctatton for Computmg Machinery To copy otherwtse, or to repubhsh, reqmres a fee and/or specific permtsslon This research was supported m part by the Nattonal Soence Foundation under Grant MCS 75-222-55 and the Office of Naval Research under

Algorithms are presented that construct the shortest connecting network, or minimal spanning tree (MST), of N points embedded in k-dimensional coordinate space. These algorithms take advantage of the geometry of such spaces to substantially reduce the computation from that required to construct MST's of more general graphs. An algorithm is also presented that constructs a spanning tree that is very nearly minimal with computation proportional to N log N for all k.

An algorithm and data structure are presented for searching a file containing N records, each described by k real valued keys, for the m closest matches or nearest neighbors to a given query record. The computation required to organize the file is proportional to kNlogN. The expected number of records examined in each search is independent of the file size. The expected computation to perform each search is proportional-to 1ogN. Empirical evidence suggests that except for very small files, this algorithm is considerably faster than other methods.

We investigate a divide-and-conquer technique in multidimensional space which decomposes a geometric problem on N points in k dimensions into two problems on N/2 points in k dimensions plus a single problem on N points in k−1 dimension. Special structure of the subproblems is exploited to obtain an algorithm for finding the two closest of N points in 0(N log N) time in any dimension. Related results are discussed, along with some conjectures and unsolved geometric problems.