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.     

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.     

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.     

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.     

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.     

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.     

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).     

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.     

New Techniques for the Computation of Linear Recurrence Coefficients

The n coefficients of a fixed linear recurrence can be expressed through its m≤2n terms or, equivalently, the coefficients of a polynomial of a degree n can be expressed via the power sums of its zeros—by means of a polynomial equation known as the key equation for decoding the BCH error-correcting codes. The same problem arises in sparse multivariate polynomial interpolation and in various fundamental computations with sparse matrices in finite fields. Berlekamp's algorithm of 1968 solves the key equation by using order of n² operations in a fixed field. Several algorithms of 1975–1980 rely on the extended Euclidean algorithm and computing Padé approximation, which yields a solution in O(n(log n)² log log n) operations, though a considerable overhead constant is hidden in the “O” notation. We show algorithms (depending on the characteristic c of the ground field of the allowed constants) that simplify the solution and lead to further improvements of the latter bound, by factors ranging from order of log n, for c=0 and c>n (in which case the overhead constant drops dramatically), to order of min (c, log n), for 2≤c≤n; the algorithms use Las Vegas type randomization in the case of 2<c≤n.     

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.     

An O(n log n) algorithm for finding all repetitions in a string

Any nonempty string of the form xx is called a repetition. An O(n log n) algorithm is presented to find all repetitions in a string of lenght n. The algorithm is based on a linear algorithm to find all the new repetitions formed when two strings are concatenated. This linear algorithm is possible because new repetitions of equal length must occur in blocks with consecutive starting positions. The linear algorithm uses a variation of the Knuth-Morris-Pratt algorithm to find all partial occurrences of a pattern within a text string. It is also shown that no algorithm based on comparisons of symbols can improve O(n log n). Finally, some open problems and applications are suggested.     

Output-Polynomial Enumeration of All Fixed-Cardinality Ideals of a Poset,Respectively All Fixed-Cardinality Subtrees of a Tree

The N cardinality k ideals of any w-element poset (k?≤?w fixed) can be enumerated in time O(Nw ³). The corresponding bound for k-element subtrees of a w-element tree is O(Nw ⁵). An algorithm is described that by the use of wildcards displays all order ideals of a poset in a compact manner, i.e. not one by one.     

A fast algorithm for multiplying min-sum permutations

The present article considers the problem for determining, for given two permutations over indices from 1 to n, the permutation whose distribution matrix is identical to the min-sum product of the distribution matrices of the given permutations. This problem has several applications in computing the similarity between strings. The fastest known algorithm to date for solving this problem executes in O(n^1.5) time, or very recently, in O(nlogn) time. The present article independently proposes another O(nlogn)-time algorithm for the same problem, which can also be used to partially solve the problem efficiently with respect to time in the sense that, for given indices g and i with 1≤g<i≤n+1, the proposed algorithm outputs the values R(h) for all indices h with g≤h<i in O(n+(i−g)log(i−g)) time, where R is the solution of the problem.     

An O(n log m) algorithm for the Josephus Problem

The Josephus Problem can be described as follows: There are n objects arranged in a circle. Beginning with the first object, we move around the circle and remove every m th object. As each object is removed, the circle closes in. Eventually, all n objects will have been removed from the circle. The order in which the objects are removed induces a permutation on the integers 1 through n. Knuth has described two O(n log n) algorithms for generating this permuation. The problem of determining a more efficient algorithm for generating the permutation is left open. In this paper we give an O(n log m) algorithm.