Knuth [1] recently showed how to estimate the size of a backtrack tree by repeatedly following random paths from the root. Often the efficiency of his method can be greatly improved by occasionally following more than...
详细信息
Knuth [1] recently showed how to estimate the size of a backtrack tree by repeatedly following random paths from the root. Often the efficiency of his method can be greatly improved by occasionally following more than one path from a node. This results in estimating the size of the backtrack tree by doing a very abbreviated partial backtrack search. An analysis shows that this modification results in an improvement which increases exponentially with the height of the tree. Experimental results for a particular tree of height 84 show an order of magnitude improvement. The measuring method is easy to add to a backtrack program.
A complete analysis is given of the number of exchanges used by the well-known Batcher’s odd-even merging (and sorting) networks. Batcher’s method involves a fixed sequence of “compare-exchange” operations, so the...
详细信息
A complete analysis is given of the number of exchanges used by the well-known Batcher’s odd-even merging (and sorting) networks. Batcher’s method involves a fixed sequence of “compare-exchange” operations, so the number of comparisons required is easy to compute, but the problem of determining how many comparisons result in exchanges has not been successfully attacked before. New results are derived in this paper giving accurate formulas for the worst-case and average values of this quantity.
An algorithm which computes the Fourier transform of a sequence of length n over GF(2m) using approximately 2nm multiplications and n2+ nm additions is developed. The number of multiplications is thus considerably sma...
详细信息
An algorithm which computes the Fourier transform of a sequence of length n over GF(2m) using approximately 2nm multiplications and n2+ nm additions is developed. The number of multiplications is thus considerably smaller than the n2multiplications required for a direct evaluation, though the number of additions is slightly larger. Unlike the fast Fourier transform, this method does not depend on the factors of n and can be used when n is not highly composite or is a prime.
Let A and B be two sparse matnces whose orders are p by q and q by r. Their product C =AB requires N nontrivial multiplications where [formula omitted]. The operation count of our algorithm is usually proportional to ...
详细信息
We compare several algorithms for sparse Gaussian elimination With column interchanges. The algorithms are all denved from the same basic elimmation scheme, and they differ mainly m Implementation details. We examine ...
详细信息
Two earlier papers descnbed the generalization of Euclid's algonthm to deal with the problem of computmg the greatest common divisor (GCD) or the resultant of a pair of polynomials. A sequel to those two papers IS...
详细信息
The decision tree complexity of computing the measure of the union of n (possibly overlapping) intervals is shown to be Ω(n log n), even if comparisons between linear functions of the interval endpoints are allowed. ...
详细信息
A class of algorithms is presented for very rapid on-line detection of occurrences of a fixed set of pattern arrays as embedded subarrays in an input array. By reducing the array problem to a string matching problem i...
详细信息
A class of algorithms is presented for very rapid on-line detection of occurrences of a fixed set of pattern arrays as embedded subarrays in an input array. By reducing the array problem to a string matching problem in a natural way, it is shown that efficient string matching algorithms may be applied to arrays. This is illustrated by use of the string-matching algorithm of Knuth, Morris and Pratt [7]. Depending on the data structure used for the preprocessed pattern graph, this algorithm may be made to run “real-time” or merely in linear time. Extensions can be made to nonrectangular arrays, multiple arrays of dissimilar sizes, and arrays of more than two dimensions. Possible applications are foreseen to problems such as detection of edges in digital pictures and detection of local conditions in board games.
暂无评论