MOTIVATION: In the maximum parsimony (MP) method, the tree requiring the minimum number of changes (discrepancy) to explain the given set of DNA or amino acid sequences is chosen to represent their evolutionary relationships. To find the MP tree, the branch-and-bound algorithm is normally used. For a partial phylogenetic-tree (one that has a subset of the organisms) the traditional algorithm assigns a cost equal to the discrepancy of the partial phylogenetic-tree. We propose a single column discrepancy heuristic which increases this cost by predicting a minimum additional discrepancy needed to attach the sequences yet to be added to the partial phylogenetic-tree. A dynamic Max-mini order of sequence addition is also proposed to quickly terminate branch-and-bound search paths that are guaranteed to lead to suboptimal solutions. RESULTS: We studied the running time of 47 problems generated from 17 data sets. The use of single column discrepancy heuristic speeded up the computation to 2.4-fold for static and 18.2-fold for dynamic search order. The improvement appeared to increase exponentially with the number of sequences. The proposed strategies are also likely to be useful in speeding up the MP tree search using heuristic searches that are based on branch-and-bound-like algorithms. CONTACT: [email protected]

The algorithm for constraint-satisfaction problems, Probe Order Backtracking, has an average running time much faster than any previously analyzed algorithm under conditions where solutions are common. The algorithm uses a probing assignment (a preselected test assignment to unset variables) to help guide the search for a solution. If the problem is not satisfied when the unset variables are temporarily set to the probing assignment, the algorithm selects one of the relations which is not satisfied by the probing assignment and selects an unset variable which affects the value of that relation. It then does a backtracking (splitting) step, where it generates subproblems by setting the selected variable each possible way. Each subproblem is simplified and then solved recursively. For random problems with v variables, t clauses, and probability p that a literal appears in a clause, the average time for Probe Order Backtracking is no more than $v^n$ when $p\geq(\ln t)/v$ plus lower-order terms. The best previous result was $p\geq\sqrt{(\ln t)/v}$. When the algorithm is combined with an algorithm of Franco that makes selective use of resolution, the average time for solving random problems is no more than $v^n$ for all values of p when $t\leq O(n^{1/3}(v/\ln v)^{2/3})$. The best previous result was $t\leq O(n^{1/3}(v/\ln v)^{1/6})$. Probe Order Backtracking also runs in polynomial average time when $p\leq 1/v$, compared with the best previous result of $p\leq 1/(2v)$. With Probe Order Backtracking, the range of p that leads to more than polynomial time is much smaller than that for previously analyzed algorithms.

Backtracking aigorithms solve problems by selecting a variable and assigning each possible value to the variable. The resulting subproblems are simplified and solved recursively. Simple backtracking selects variables in a fixed order. Clause order backtracking selects variables from the first nontrivial clause that has not yet been satisfied. Formulas are given for the average time used by clause order backtracking when solving random CNF satisfiability problems, where the problem sets have v variables, t clauses, and a probability p of a literal being in a clause. The average time for clause order backtracking is always less than that for simple backtracking. It leads to polynomial time under many conditions where simple backtracking uses exponential average time. Cases where clause order backtracking uses average time less than $v^n $ (in the limit of v going to infinity) include $p < {1 / {(2v)}}e^{{{[(n - 1)\ln v - \ln t]} / t}} $ and $p > \sqrt {[\ln t + {{{{(\ln v)} / 2}]} / v}} $. (The second result needs a slight increase in the coefficient of $\ln t$ when t increases faster than $v^{\ln v} $.)

The computation of a strong generating set for a permutation group acting on a set $\Omega $ of n points is the fundamental operation that underlies most of the algorithms in computational group theory. Sims gave a change of basis algorithm that transforms a strong generating set relative to one ordering of $\Omega $ into a strong generating set relative to a different ordering. Base change is crucial for many of the important algorithms that have been implemented in the Cayley system, and is also important for many applications of computational group theory to combinatorial and search problems. Sims’s base change has worst-case time $O(n^5 )$. The main result of this paper is a new change of basis algorithm that has worst-case time $O(n^3 )$.

This paper gives exponential lower bounds for the average time of an algorithm based on a simplified version of the pure literal rule from the Davis–Putnam procedure. It is shown that this algorithm requires an average time that is exponential in v, the number of variables, when p, the probability that a literal is in a clause, is proportional to $1/v$ and t, the number of clauses in the predicate, is at least a linear function of v. The time is greater than any polynomial in v over a somewhat larger range of parameters. For the two cases $t = \Theta (\ln v)$ and $p = O(\ln v/v^{3/2} )$, the results of this lower-bound analysis are the same (to within a constant factor) as the upper-bound results in [SIAM J. Comput., 14 (1985), pp. 943–953]. The results of this and other papers show that the fastest analyzed algorithm for random satisfiability problems depends on the parameters of the distribution. Backtracking, the pure literal rule, and the new algorithm of Iwama [Report KSU/ICS 88-01, Institute of Computer Science, Kayoto Sangyo University, Kyoto, Japan, 1988 each have a large region of parameter setting where it is exponentially faster than the other two.

Abstract A fast algorithm for performing simplification and matching is described. The algorithm gives an improvement of up to an order of magnitude on suitable problems. It makes use of a dag data structure and tag fields to avoid redundant matches. Performance studies were done to determine the relative importance of various features in improving the running time.

In estimating minimax values, an important topic in the study of heuristic game tree searches, a pathological phenomenon sometimes results when the conventional minimax procedure is used as a back-up process. In this paper exact methods are derived for two different games, one using product-propagation rules as a back-up process and another not using any back-up process. The method of estimating minimax values in a heuristic game tree search should depend on both the static evaluation function and the structure of the game tree; it can be very different for different games.

For a simple parameterized model of conjunctive normal form predicates, we show that a simplified version of the Davis–Putnam procedure can, for many values of the parameters, solve the satisfiability problem in polynomial average time. Let v be the number of variables, $t(v)$ the number of clauses in a predicate, and $p(v)$ the probability that a given literal appears in a clause ($p(v)$ is the same for all literals). Let $\varepsilon $ be any small positive constant and n any large positive integer. Then a version of the Davis–Putnam procedure that uses only backtracking and the pure literal rule uses average time that is polynomial in the problem size when any of the following conditions are true for large v. (1) $t(v) \leqq n\ln v$; (2) $t(v) \geqq \exp (\varepsilon v)$; (3) $p(v) \geqq \varepsilon $; or (4) $p(v) \leqq n (\ln v/ v)^{3/2} $. Until recently the best previous bounds for cases (1) and (4) were $t(v) \leqq (\ln\ln v)/(\ln3)$ and $p(v) \leqq \exp ( - v\ln \ln v)$. These results show that the problem types for which the pure literal rule works well are quite different from those for which backtracking works well. Our present knowledge suggests this random problem sets with $t(v)$ somewhat larger than v and with $p(v)$ somewhat larger than $v^{ - 1} $ are particularly difficult to solve.

Abstract A methodology and associated notation for designing compiler front ends, and in particular the interface between the parser and the semantic routines, is described. The methodology leads to a clean, easy to understand, documentable design. The notation is similar to an attribute grammar, but its purpose is to document the first pass of a specific compiler, rather than to describe the semantics of a language. It is designed to be accessible to non‐specialists, easy to learn, and natural. It can be used with or without software support. The notation was used during the development of a large compiler, and to assist in the transfer of the compiler to the group that will maintain it. Experience with the notation indicates that it meets its goals.

The search rearrangement backtracking algorithm of Bitner and Reingold [Comm. ACM, 18 (1975), pp. 651–655] introduces at each level of the backtrack tree a variable with a minimal number of remaining values; search order may differ on different branches. For conjunctive normal form formulas with v variables, s literals per term $(s \geqq 3)$, and $v^\alpha $ terms $((s/2) < \alpha < s)$, the average number of nodes in a search rearrangement backtrack tree is $\exp [\Theta (v^{(s - \alpha - 1)/(s - 2)} )]$ (i.e., for some positive constants $a_1 ,a_2 $, and $v_0 $, when $v \geqq v_0 $ the number of nodes is between $\exp (a_1 v^{(s - \alpha - 1)/(s - 2)} )$ and $\exp (a_2 v^{(s - \alpha - 1)/(s - 2)} )$. For $1 < \alpha \leqq s/2$ the average number of nodes is between $\exp [\Theta (v^{(s - \alpha - 1)/(s - 2)} )]$ and $\exp [\Theta ((\ln v)^{(s - 1)/(s - 2)} v^{(s - \alpha - 1)/(s - 2)} )]$. This compares with $\exp [\Theta (v^{(s - \alpha )/(s - 1)} )]$ for ordinary backtracking. For $1 < \alpha < s$, simple search rearrangement has approximately the same effect on speeding up backtracking as does reducing the problem complexity by decreasing the number of literals per term by one. Thus simple search rearrangement backtracking leads to a dramatic improvement in the expected running time.

In this paper we report the results of experimental studies of zero-level, one-level, and two-level search rearrangement backtracking. We establish upper and lower limits for the size problem for which one-level backtracking is preferred over zero-level and two-level methods, thereby showing that the zero-level method is best for very small problems. The one-level method is best for moderate size problems, and the two-level method is best for extremely large problems. Together with our theoretical asymptotic formulas, these measurements provide a useful guide for selecting the best search rearrangement method for a particular problem.

Formulas are given for the expected number of nodes in the backtrack tree that is generated while searching for all the solutions of a random predicate. The most general formulas apply to selection from any set of predicates that obeys the following conditions. Each predicate is the conjunction of t terms selected from a set of terms T. For any subset $T' \leqq T$, the probability that the predicate contains only terms from $T'$ depends only on the size of $T'$. The set T must remain unchanged if each variable $x_i $ is replaced by $p_i (x_i )$, where $p_i $ is a permutation function. The time needed to evaluate the general formulas is proportional to v, the number of variables in the predicate. More detailed consideration is given to predicates whose terms are random disjunctive clauses with s literals, $t = v^\alpha $ for some $1 < \alpha < s$, and the random selections are done with repetition. For this case the expected number of nodes is $\exp [O(v^{(s - \alpha )/(s - 1)} )]$. (Complete enumeration results in $\exp [O(v)]$ nodes.) Thus the average time for backtracking in this model is exponential with a sublinear exponent.

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.

TWO time-sharing models are described.One is the conventional round-robin model in which each customer receives at most q seconds of service at a time.If this completes his service requirement, he leaves the system; otherwise he joins the end of the queue to await his next turn.The second model is a modification of the round-robin system in which the amount of service per pass depends on the rate at which programs arrive in the system.The models are analyzed under the assumption of constant, nonzero overhead when the processor swaps one program for another.Expressions are derived for the mean waiting time in queue as a function of service requirement and for the mean system cost due to waiting time in queue.

The utilization of space and the running speed of the buddy system are considered Equations are derived that give various statistical properties of the buddy system. For the bottom level with Poisson requests and exponential service times the expected amount of space wasted by pairing full cells with empty cells is about 0.513 ρ 1/2 and the mean time between requests from the bottom level to the next level is about 1.880 ρ 1/2 λ -1 , where ρ is the mean number of blocks in use on the bottom level and λ -1 is the mean time between requests for blocks on the bottom level. The results of a number of simulations of the buddy system are also given and compared with the analytical studies.