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

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.

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.

What constitutes cheating on programming assignments? What methods can be used to detect cheating? What should be done with offenders? How can cheating be eliminated in programming courses? These are all pertinent questions, but they are directed more towards treating symptoms rather than towards correcting some very fundamental problems.

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.