19627656
A Minimum Area VLSI Network for O(log n) Time Sorting
A generalization of a known class of parallel sorting algorithms is presented, together with a new interconnection to execute them. A VLSI implementation is also proposed, and its area-time performance is discussed. It is shown that an algorithm in the class is executable in O(log n) time by a chip occupying O(n2) area. The design is a typical instance of a ``hybrid architecture,'' resulting from the combination of well-known VLSI networks as the orthogonal trees and the cube-connected cycles; it also provably meets the AT2 = ¿(n2 log2 n) lower bound for sorters of n words of length (1 + ¿) log n (¿ ≫ 0).
40454105
Area-Time Optimal VLSI Integer Multiplier with Minimum Computation Time
According to VLSI theory, [logn, √n] is the range of computation times for which there may exist an AT2-optimal multiplier of n-bit integers. Such networks were previously known for the time range [Ω(log2n), 0(√n)]; in this paper we settle this theoretical question, by exhibiting a-class of AT2-optimal multipliers with computation times [Ω(logn), 0(n1/2)]. Our designs are based on the DFT on a Fermat ring, whose elements are represented in a redundant radix-4 form to ensure 0(1) addition time.
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
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.
18686062
Sequencing-by-hybridization revisited: the analog-spectrum proposal
All published approaches to DNA sequencing by hybridization (SBH) consist of the biochemical acquisition of the spectrum of a target sequence (the set of its subsequences conforming to a given probing pattern) followed by the algorithmic reconstruction of the sequence from its spectrum. In the "standard" or "uniform" approach, the probing pattern is a string of length L and the length of reliably reconstructible sequences is known to be m/sub len/ = O(2/sup L/). For a fixed microarray area, higher sequencing performance can be achieved by inserting nonprobing gaps ("wild-cards") in the probing pattern. The reconstruction, however, must cope with the emergence of fooling probes due to the gaps and algorithmic failure occurs when the spectrum becomes too densely populated, although we can achieve m/sub comp/ = O(4/sup L/). Despite the combinatorial success of gapped probing, all current approaches are based on a biochemically unrealistic spectrum-acquisition model (digital-spectrum). The reality of hybridization is much more complex. Departing from the conventional model, in this paper, we propose an alternative, called the analog-spectrum model, which more closely reflects the biochemical process. This novel modeling reestablishes probe length as the performance-governing factor, adopting "semidegenerate bases" as suitable emulators of currently inadequate universal bases. One important conclusion is that accurate biochemical measurements are pivotal to the success of SBH. The theoretical proposal presented in this paper should be a convincing stimulus for the needed biotechnological work.
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.
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.