14662605
Bounds to Complexities of Networks for Sorting and for Switching
Abstract : A network which sorts n numbers when used to sort numbers of only two sizes, 0 and 1, can be regarded as forming the n frontal (unate) symmetric boolean functions of n arguments. When sorting networks are constructed from comparator modules they appear to require: (1) delay time or number of levels of order (log of n to the base 2) squared, (2) size or number of elements of order (log of n to the base 2) squared, and (3) formula length or number of literals of order n (log of n to the base 2). If one permits the use of negations in constructing the corresponding boolean functions, these three measures of complexity can be reduced to the orders of log of n to the base 2, n, and n to the 5th power respectively. The latter network however is incapable of sorting numbers and may be thought of as merely counting the number of inputs which are 1. One may incorporate this network, however, in a larger network which does sort and in time proportional to only log of n to the base 2. (Author)
32387126
Finding the Intersection of two Convex Polyhedra
Abstract Given two convex polyhedra in three-dimensional space, we develop an algorithm to (i) test whether their intersection is empty, and (ii) if so to find a separating plane, while (iii) if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in time O ( n log n ), where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with (iii) (constructing the intersection) is based upon the fact that if a point in the intersection is known, then the entire intersection is obtained from the convex hull of suitable geometric duals of the two polyhedra taken with respect to this point.
215848405
The cube-connected cycles: a versatile network for parallel computation
An interconnection pattern of processing elements, the cube-connected cycles (CCC), is introduced which can be used as a general purpose parallel processor. Because its design complies with present...
206394014
Holographic dispersal and recovery of information
A simple scheme for dispersal and recovery of digital information based on the discrete Fourier transform is discussed. The author presents a different implementation of M.O. Rabin's (J. ACM, vol.36, no.2, p.335-48, Apr. 1989) scheme, whose recovery cost is O(log m+k) operations per character, assuming m= Theta (n); for example, when k= Theta (log n), this cost drops from O(m) to O(log m) per character. Since the implementation is based on the Fourier transform, it is termed holographic. >
12263445
Approximation algorithms for convex hulls
The problem of constructing the convex hull of a finite point set in a Euclidean space arises in many applications. In this paper we study a set of algorithms for constructing approximate convex hulls. We show that an E-approximate hull of N points in the plane can be constructed in O(n + I/e) time. The planar algorithm has been implemented and is very fast on point sets that arise in practice. The method can be generalized to compute hulls of point sets in higher dimensional spaces. CR
205093415
Dynamic Planar Point Location with Optimal Query Time
We present a new dynamic technique for locating a point in a convex planar subdivision whose n vertices lie on a fixed set of N horizontal lines. The supported update operations are insertion/deletion of vertices and edges, and (horizontal) translation of vertices. Our method achieves query time O(log n + log N), space O(N + n log N), and insertion/deletion time O(log n log N). Hence, for N=O (n), the query time is O(log n), which is optimal. The proposed technique, based on the trapezoid method, provides an efficient solution to many significant applications where the most frequent operation is the point location query, while updates are more rarely executed.
62245037
Processor—Time Tradeoffs under Bounded-Speed Message Propagation: Part I, Upper Bounds
Upper bounds are derived for the processor—time tradeoffs of machines such as linear arrays and two-dimensional meshes, which are compatible with the physical limitation expressed by bounded-speed propagation of messages (due to the finiteness of the speed of light). It is shown that parallelism and locality combined may yield speedups superlinear in the number of processors. The speedups are inherent, due to the optimality of the obtained tradeoffs as established in a companion paper.Simulations of multiprocessor machines are developed by analogous machines with fewer processors. A crucial role is played by the hierarchical nature of the memory system. A divide-and-conquer technique for hierarchical memories is developed, based on the graph-theoretic notion of a topological separator. For multiprocessors, this technique also requires a careful balance of memory access and interprocessor communication costs, which leads to nonintuitive orchestrations of the simulation process.
41033149
Parallel Restructuring and Evaluation of Expressions
Abstract In this paper we describe a boolean network of size O ( N 2 log N ) which accepts a fully parenthesized N -variable expression over a given semiring and produces its value in O (log N ) time. The network consists of two components: a preprocessor and a universal evaluator. The preprocessor computes the destinations of the expression terms and routes them to the correct input terminals of the universal evaluator.
1952504
Data structures and algorithms for the string statistics problem
Given a textstringx of lengthn, theMinimal Augmented Suffix Tree T (x) ofx is a digital-search index that returns, for anyquery stringw and in a number of comparisons bounded by the length ofw, the maximum number of nonoverlapping occurrences ofw inx. It is shown that, denoting the length ofx byn, T(x) can be built in timeO(n log2n) and spaceO(n logn), off-line on a RAM.
37382391
Horizons of Parallel Computation
This paper considers the ultimate impact of fundamental physical limitations---notably, speed of light and device size---on parallel computing machines. Although we fully expect an innovative and very gradual evolution to the limiting situation, here we take the provocative view of exploring the consequences of the accomplished attainment of the physical bounds. The main result is that scalability holds only for neighborly interconnections, such as the square mesh, of bounded-size synchronous modules, presumably of the area-universal type. We also discuss the ultimate infeasibility of latency-hiding, the violation of intuitive maximal speedups, and the emerging novel processor-time tradeoffs.
930169
Sequencing-by-hybridization at the information-theory bound: an optimal algorithm
In a recent paper [PFU99) we have introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a well defined periodic pattern. It was shown in [PFU99] that the performance of the gapped-probe scheme (in terms of the length of a sequence that can be uniquely reconstructed using a given library size of probes) is significantly better than the standard scheme based on oligomer probes.
In this paper we present and analyze a new, more powerful, sequencing algorithm for the gapped-probe scheme. We prove that the new algorithm exploits the full potential of the SBH technology with high-confidence performance, that comes within a small constant factor (about 2) of the information-theory bound. Moreover, this performance is achieved while maintaining running time linear in the target sequence length.