On some algorithmic problems regarding the hairpin completion

We consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem of the hairpin and iterated hairpin completion of a language. We propose an O(nf(n)) and O(n²f(n)) time recognition algorithm for the hairpin completion and iterated hairpin completion, respectively, of a language recognizable in O(f(n)) time. We show that the n factor is not needed in the case of hairpin completion of regular and context-free languages. The n² factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us.     

On the complexity of calculating factorials

It is shown that n! can be evaluated with time complexity O(log log nM (n log n)), where M(n) is the complexity of multiplying two n-digit numbers together. This is effected, in part, by writing n! in terms of its prime factors. In conjunction with a fast multiplication this yields an O(n(log n log log n)²) complexity algorithm for n!. This might be compared to computing n! by multiplying 1 times 2 times 3, etc., which is ω(n² log n) and also to computing n! by binary splitting which is O(log nM(n log n)).     

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n²/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n²/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n²/log n) processors in the CRCW model and in time O(log²n) with O(n²/log n log log n) processors in the EREW model.     

The measure problem for rectangular ranges in d-space

Klee recently posed the question: find an efficient algorithm for computing the measure of a set of n intervals on the line, and the analog for n hyperrectangles (ranges) in d-space. The one-dimensional case is easily solved in O(n log n) and Bentley has proved an O(n^d?1log n) algorithm for dimension d ≥ 2. We present an algorithm for Klee's measure problem that has a worst-case running time of only O(n^d?1) for d?3. While Bentley's algorithm is based on segment trees and requires only linear storage for any dimension, the new method is based on quad-trees and requires quadratic storage for d > 2.     

An Efficient Algorithm for the Complex Roots Problem

Given a univariate polynomialf(z) of degreenwith complex coefficients, whose norms are less than 2^min magnitude, the root problem is to find all the roots off(z) up to specified precision 2^−μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexityO(nlog⁵nlogB), whereb= χ + μ, and χ = max{n,m}. This improves on the previous best known algorithm of Pan for the problem, which has complexityO(n²log²nlog(m+ μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation off, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = ⌈n(B+ logn+ 3)⌉ bits of the binary representations of the real and imaginary parts of each of the coefficients off. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where[formula]and[formula]Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor ofM(φ) (whereM(ψ) =O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and “centered” points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel timeO(log⁶nlogB) usingnprocessors.     

Minimum Range Balanced Cuts via Dynamic Subset Sums

We find the balanced cut in a graph that minimizes the maximum difference between edge lengths in timeO(m + n² log n), improving a previousO(m + n^2.5) bound. We use subroutines for solving a dynamic subset sum problem in timeO(l log l log n) per operation in the fully dynamic setting, or in timeO(l log n) per operation in thesemi-onlinesetting in which one can predict a superset of future deletions.     

Centroids,Representations, and Submodular Flows

The notion of centroid of a tree is generalized to apply to an arbitrary intersecting family of sets. Centroids are used to construct a compact representation for any intersecting family of sets, as well as any crossing family. The size of the representation for a family on n elements is O(n²), compared to size O(n³) for previous representations. Efficient algorithms to construct the representation are given. For example on a network of n vertices and m edges, the representation of all minimum cuts uses O(m log(n²/m)) space; it is constructed in O(nm log(n²/m)) time (this is the best-known time for finding one minimum cut). The representation is used to improve several submodular flow algorithms. For example a minimum-cost dijoin is found in time O(n²m); as a result a minimum-cost planar feedback are set is found in time O(n³). The previous best-known time bounds for these two problems are both a factor n larger.     

Efficient algorithms for checking the equivalence of programs in interrupt handling models

The problem of equivalence of interrupt handling programs in two algebraic models is studied. Program operators are divided into two classes, namely, the classes of basic operators and interrupt handling operators. The first model obeys the absorption law, i.e., each basic operator suppresses the result of application of any interrupt handling operator. This means that, if the interrupt handling is successfully finished and the control is passed to basic operators, then the result of interrupt handling has no influence on the program output. An algorithm that solves the problem of equivalence in the above model in O(n ²log n) operations is suggested. The other model obeys the absorption law and satisfies the commutative property for basic operators. For this model, we also propose an algorithm that checks the equivalence of programs in O(n ⁴log n) operations.     

Systolic implementation of the lattice algorithm for least squares linear prediction problems

We present a linear systolic array of O(n) cells that solves the least squares linear prediction problem in time O(n) via an algorithm based on the so-called lattice algorithm. The total storage required is O(n) words, i.e., only a constant number of words are needed at each cell.     

An Improved Algorithm for the Traveler′s Problem

In a paper in Journal of Algorithms13 (1992), 148-160, Hirschberg and Larmore introduced the traveler′s problem as a subroutine for constructing the B-tree. They gave an O(n^5/3 log^1/3n) time algorithm for solving the traveler′s problem of size n. In this paper, we improve their time bound to O(n^3/2 log n). As a consequence, we build a B-tree in O(n^3/2 log²n) time as compared to the O(n^5/3 log^4/3n) time algorithm of Hirschberg and Larmore.     

An O(n log n) unidirectional distributed algorithm for extrema finding in a circle

In this paper we present algorithms, which given a circular arrangement of n uniquely numbered processes, determine the maximum number in a distributive manner. We begin with a simple unidirectional algorithm, in which the number of messages passed is bounded by 2 n log n + O(n). By making several improvements to the simple algorithm, we obtain a unidirectional algorithm in which the number of messages passed is bounded by 1.5nlogn + O(n). These algorithms disprove Hirschberg and Sinclair's conjecture that O(n²) is a lower bound on the number of messages passed in undirectional algorithms for this problem. At the end of the paper we indicate how our methods can be used to improve an algorithm due to Peterson, to obtain a unidirectional algorithm using at most 1.356nlogn + O(n) messages. This is the best bound so far on the number of messages passed in both the bidirectional and unidirectional cases.     

An algorithm for parallel evaluation of functions

A technique is shown for speeding up parallel evaluation of functions. An algorithm is presented that evaluates powers xⁿ in time O(√log n) using O(n) processors and certain preprocessed data, while the known algorithms take [log₂n] steps of multiplication or addition.     

Optimal multiway split trees

A class of multiway split trees is defined. Given a set of n weighted keys and a node capacity m, an algorithm is described for constructing a multiway split tree with minimum access cost. The algorithm runs in time O(mn⁴) and requires O(mn³) storage locations. A further refinement of the algorithm enables the factor m in the above costs to be reduced to log m.     

Binary tree algebraic computation and parallel algorithms for simple graphs

In this paper we define the binary tree algebraic computation (BTAC) problem and develop an efficient parallel algorithm for solving this problem. A variety of graph problems (minimum covering set, minimum r-dominating set, maximum matching set, etc.) for trees and two terminal series parallel (TTSP) graphs can be converted to instances of the BTAC problem. Thus efficient parallel algorithms for these problems are obtained systematically by using the BTAC algorithm. The parallel computation model is an exclusive read exclusive write PRAM. The algorithms for tree problems run in O(log n) time with O(n) processors. The algorithms for TTSP graph problems run in O(log m) time with O(m) processors where n (m) is the number of vertices (edges) in the input graph. These algorithms are within an O(log n) factor of optimal.     

Difference sets and shifted primes

We show that if A is a subset of {1, …, n} which has no pair of elements whose difference is equal to p ? 1 with p a prime number, then the size of A is O(n(log log n)^{?c(log log log log log n)}) for some absolute c > 0.     

Essentially optimal computation of the inverse of generic polynomial matrices

We present an inversion algorithm for nonsingular n×n matrices whose entries are degree d polynomials over a field. The algorithm is deterministic and, when n is a power of two, requires O^∼(n³d) field operations for a generic input; the soft-O notation O^∼ indicates some missing log(nd) factors. Up to such logarithmic factors, this asymptotic complexity is of the same order as the number of distinct field elements necessary to represent the inverse matrix.     

A Randomized Parallel Algorithm for Planar Graph Isomorphism

We present a parallel randomized algorithm running on aCRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms inO(log² n) time withn^{1 + ε}processors, for any ε > 0). Ifnis the number of vertices, our algorithm takesO(log(n)) time with processors and with a probability of failure of 1/nat most. The algorithm needs 2 · log(m) − log(n) + O(log(n)) random bits. The number of random bits can be decreased toO(log(n)) by increasing the number of processors ton^{3/2 + ε}, for any ε > 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput.20(1991), 1128–1147), which requiresn⁴randomized processors orn⁵deterministic processors.     

Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (J. Comput. System Sci. 51 (3), 390–399, 1995) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once, in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present:

1. an O(n ²) algorithm performing O(logn·log e(P)) comparisons
2. an O(n ^2:5) algorithm performing at most (1+?) log e(P)+O _? (n) comparisons
3. an O(n ^2:5) algorithm performing O(log e(P)) comparisons.

All our algorithms can be implemented in such a way that their computational bottleneck is confined in a preprocessing phase, while the sorting phase is completed in O(q)+O(n) time, where q denotes the number of comparisons performed.     

On parallel hashing and integer sorting

The problem of sorting n integers from a restricted range [1…m], where m is a superpolynomial in n, is considered. An o(n log n) randomized algorithm is given. Our algorithm takes O(n log log m) expected time and O(n) space. (Thus, for m = n^polylog(n) we have an O(n log log n) algorithm.) The algorithm is parallelizable. The resulting parallel algorithm achieves optimal speedup. Some features of the algorithm make us believe that it is relevant for practical applications. A result of independent interest is a parallel hashing technique. The expected construction time is logarithmic using an optimal number of processors, and searching for a value takes O(1) time in the worst case. This technique enables drastic reduction of space requirements for the price of using randomness. Applicability of the technique is demonstrated for the parallel sorting algorithm and for some parallel string matching algorithms. The parallel sorting algorithm is designed for a strong and nonstandard model of parallel computation. Efficient simulations of the strong model on a CRCW PRAM are introduced. One of the simulations even achieves optimal speedup. This is probably the first optimal speedup simulation of a certain kind.     

A note on scheduling jobs with equal processing times and inclusive processing set restrictions

We consider the problem of scheduling n jobs on m parallel machines with inclusive processing set restrictions. Each job has a given release date, and all jobs have equal processing times. The objective is to minimize the makespan of the schedule. Li and Li (2015) have developed an O(n²+mn log?n) time algorithm for this problem. In this note, we present a modified algorithm with an improved time complexity of O(min{m, log?n} ? n log?n).