Search

The article presents information on the publication of a book "Applied Statistics, Algorithms," relevant to statistics, by the Royal Statistical Society in cooperation with the Science Research Council's Working Party on Statistical Computing. A policy statement describing the editorial policy appears in "Applied Statistics," Vol. 1. No. 1 (1968). A support paper describing the expected contents of the external specification and making recommendation for the layout of algorithms and for programming strategy will appear in the following issue.

The paper describes a scheme for symbolic manipulation of index expressions which arise as a by-product of the symbolic manipulation of expressions in the matrix calculi described by the authors in a previous paper. This scheme attempts program optimization by transforming the original algorithm rather than the machine code. The goal is to automatically generate code for handling the tedious address calculations necessitated by complicated data structures. The paper is therefore preoccupied with "indexing by position." The relationship of "indexing by name" and "indexing by position" is discussed. [ABSTRACT FROM AUTHOR]

A comprehensive system for transformational grammar has been designed and implemented on the IBM 360/67 computer. The system deals with the transformational model of syntax, along the lines of Chomsky's Aspects of the Theory of Syntax. The major innovations include a full, formal description of the syntax of a transformational grammar, a directed random phrase structure generator, a lexical insertion algorithm, an extended definition of analysis, and simple problem-oriented programming language in which the algorithm for application of transformations can be expressed. In this paper we present the system as a whole, first discussing the general attitudes underlying the development of the system, then outlining the system and discussing its more important special features. References are given to papers which consider some particular aspect of the system in detail. [ABSTRACT FROM AUTHOR]

Presents several letters to the editor about the computing machinery. Dissatisfaction with the quality and nature of the average technical paper presented at the Joint Computer Conferences; Comment on the article "One-Pass Compilation of Arithmetic Expressions for a Parallel Processor," by Harold S. Stone; Use of a coordinate system or characteristic indices for the progress of an algorithm.

Affix grammars are two-level grammars which are similar to van Wijngaarden's two-level grammars used in the definition of Algol 68. Affix grammars are shown by Koster to be equal in power to van Wijngaarden grammars. They are much more suited to parsing than are the latter, however. Koster, the inventor of affix grammars, suggests a top-down scheme for parsing them, based on recursive procedures. This paper presents a bottom-up scheme for parsing them, based on an extension of Floyd Production Language (FPL). Included is an algorithm, similar to that of DeRemer's, for converting a large class of affix grammars into FPL. The paper concludes by discussing briefly the applicabilities of the conversion algorithm and affix grammars in general, and some possible extensions to Koster's definition of affix grammars. [ABSTRACT FROM AUTHOR]

Clenshaw-Curtis quadrature is a particularly important automatic quadrature scheme for a variety of reasons, especially the high accuracy obtained from relatively few integrand values. However, it has received little use because it requires the computation of a cosine transformation, and the arithmetic cost of this has been prohibitive. This paper is in two parts; a companion paper, "II Computing the Cosine Transformation," shows that this objection can be overcome by computing the cosine transformation by a modification of the fast Fourier transform algorithm. This first part discusses the strategy and various error estimates, and summarizes experience with a particular implementation of the scheme. [ABSTRACT FROM AUTHOR]

In a companion paper to this, "I Methodology and Experiences," the automatic Clenshaw-Curtis quadrature scheme was described and how each quadrature formula used in the scheme requires a cosine transformation of the integrand values was shown. The high cost of these cosine transformations has been a serious drawback in using Clenshaw-Curtis quadrature. Two other problems related to the cosine transformation have also been troublesome. First, ... conventional computation of the cosine transformation by recurrence relation is numerically unstable, particularly at the low frequencies which have the largest effect upon the integral. Second, in case the automatic scheme should require refinement of the sampling, storage is required to save the integrand values after the cosine transformation is computed. This second part of the paper shows how the cosine transformation can be computed by a modification of the fast Fourier transform and all three problems overcome. The modification is also applicable in other circumstances requiring cosine or sine transformations, such as polynomial interpolation through the Chebyshev points. [ABSTRACT FROM AUTHOR]

Conflicts in scheduling can be treated as defining an undirected linear graph independently of the relation of the activities in conflict to additional constraints of time and space. Each connected component of such a graph, which can be found by on algorithm described by Gotlieb and Corneil, corresponds to a set of events that must be scheduled at different times. [ABSTRACT FROM AUTHOR]

The use of the Kleene regular expression notation for describing algebraic language syntax, in particular of ALGOL is described in this paper. A FORTRAN II computer program for carrying out the elimination algorithm of Gorn, similar to Gaussian elimination for linear systems of algebraic equations, is described. This was applied to numerous smaller languages, including some sublanguages of ALGOL. A hand calculation result of the application of the algorithm to all of ALGOL is given, thus expressing the Revised ALGOL 1960 syntax in completely nonrecursive terms, as far as its context-free portion is concerned. This description in many ways is far more intuitively understood than the previous recursive description, it is suggested. The paper also includes results of the machine program, which does not include a simplification algorithm. [ABSTRACT FROM AUTHOR]

This paper presents a new approach to the analysis of performance of the various key-to-address transformation methods. In this approach the keys in a file arc assumed to have been selected from the key space according to a certain probabilistic selection algorithm. All files with the same number of keys selected from this key space will be suitably weighted in accordance with the algorithm, and the average performance of the transformation methods on these files will be used as the potential of these methods. Using this analysis, methods with the same overall performance can be classified and key distributions partial to certain transformations can be identified. All this can be done analytically. The approach is applied to a group of transformation methods using files whose keys are selected randomly. [ABSTRACT FROM AUTHOR]

The article presents several research papers relating to algorithms. The paper "Greatest Common Divisor of n Integers and Multipliers" presents an algorithm which calculates the greatest common divisor, IGCD, of n integers. Details of the method and comparisons to other algorithms are also given. The algorithm is a new version of the Euclidean algorithm for n integers. The n-1 calculations of the greatest common divisor of two integers is accomplished by means of a modified version of the Blankinship algorithm. The paper "Exponential Integral Ei (x)" presents the results of one phase of research carried out at the Jet Propulsion Laboratory, California Institute of Technology, under Contract NAS7-100, sponsored by the National Aeronautics and Space Administration. It presents an algorithm which was compiled and executed without any modification on a UNIVAC 1108 computer. An unfortunate precedent has been set in several recent algorithms of using an illegal FORTRAN construction.

This paper presents a canonical form for context-sensitive derivations and a parsing algorithm which finds each context-sensitive analysis once and only once. The amount of memory required by the algorithm is essentially no more than that required to store a single complete derivation. In addition, a modified version of the basic algorithm is presented which blocks infinite analyses for grammars which contain loops. The algorithm is also compared with several previous parsers for context-sensitive grammars and general rewriting systems, and the difference between the two types of analyses is discussed. The algorithm appears to be complementary to an algorithm by S. Kuno in several respects, including the space-time trade-off and the degree of context dependence involved. [ABSTRACT FROM AUTHOR]

An algorithm is described which accepts an arbitrary context-free grammar and constructs a bounded-context parser for it whenever such a parser exists. In the first part of the paper the definition of a context-free grammar and the working of a bounded-context parser are recalled. The notion of reduction class for a context-free gram- mar is then introduced and its connection with the structure of a bounded-context parser is indicated. Next, pushdown automata which generate the different reduction classes of a Context-free grammar ore defined. Finally, the algorithm is described; it essentially carries out an exhaustive study of all possible runs of the pushdown automata generating the reduction classes, In the second part, the utility of the algorithm is discussed in the light of the experience gained from its use in compiler design. The algorithm is claimed to be particularly useful in the simultaneous design of a language and a compiler for it. [ABSTRACT FROM AUTHOR]

The article presents comments on several algorithms. The algorithms offer information on factorial analysis of variance, shortest-path forest with topological ordering, permanent function of a square matrix I and II, generation of random permutations, complex error function, associated legendre functions of the first kind for real or imaginary arguments, computation of Fourier coefficients, generalized least squares fit by orthogonal polynomials and generation of permutations in pseudolexicographic order.

The problem classically titled "The Examination Schedule Problem" takes various forms in the literature. Most of these formulations can be presented in the terminology of classical Network Theory. One such formulation is: Given a nondirected network, partition its nodes into a minimal number of subsets such that no two members of the same subset are connected by an An obvious lower limit to this number is the size of the largest strongly connected subgraph. Kirchgassner proved that an upper limit is this size plus one. One logical extension of the previous work is the introduction of variable length examinations where W(I) is the number of periods for exam I. The object of this paper is to generalize the definition of largest strongly connected subgraph to include the weighting of nodes, to present an approximate algorithm which usually finds the largest strongly connected subgraph, and to discuss the application of this algorithm to the solution of school scheduling and exam scheduling problems. [ABSTRACT FROM AUTHOR]

The QR iteration for the eigenvalues of a symmetric tridiagonal matrix can be accelerated by incorporating a sequence of origin shifts. The origin shift may be either subtracted directly from the diagonal elements of the matrix or incorporated by means of an implicit algorithm. Both methods have drawbacks: the direct method can unnecessarily degrade small eigen-values, while the implicit method can effectively loose the shift and thereby retard the convergence. This paper presents a new method which has neither drawback. [ABSTRACT FROM AUTHOR]

The article offers news briefs related to the Association for Computing Machinery (ACM) in the U.S. The United States of America Standards Institute Inc. (USASI) changed its name to the American National Standards Institute (ANSI). A symposium on mathematical software will be held at Purdue University in West Lafayette, Indiana will be held from April 1 -3, 1970. The Second Annual ACM Symposium on Theory of Computing will be held in Northampton Massachusetts from May 4-6, 1970.

This paper deals with algorithms concerning arithmetic expressions used in a FORTRAN IV compiler for a HITAC.5020 computer having n accumulators. The algorithms generate an object code which minimizes the frequency of storing and recovering the partial results of the arithmetic expressions in cases where there are several accumulators. [ABSTRACT FROM AUTHOR]

As linear programming models grow bigger and bigger in size, much actual data that must be memorized is often put on magnetic tape or disk, and consequently there is an improportionately fast rise in the consumption of computer time. To cut down this expense, on ever increasing effort Is mode to design more efficient algorithms. This paper is meant to support the effort. If is attempted to find some characteristics of the way pivot column is found. The number of repetitions of a certain transfer of data from tape to core memory is considered. After some simplification, the problem is restated in a general way. The generating function of the probability distribution and the moment generating function of the number of repetitions is found. Asymptotic formulas are given for the moments using result from a paper of S. Narumi [1]. The results may be applied to write very efficient routines that search for an extreme value in a table. Formulas provide a means of calculating the computer timings in this case. [ABSTRACT FROM AUTHOR]

As part of an effort to design and implement a Fortran compiler on the ILLIAC IV, an extended Fortran, called IVTRAN, has been developed. This language provides a means of expressing data and control structures suitable for exploiting ILLIAC IV parallelism. This paper reviews the hardware characteristics of the nine and singles out unconventiona features which could be expected to influence langluage (and compiler) design. The implications of these features for data layout and algorithm structure are discussed, and the conclusion is drawn that data allocation rather than code structuring is the crucial ILLIAC optimization problem. A satisfactory method of data allocation is then presented. Language structures to utilize this storage method and express parallel algorithms are described. [ABSTRACT FROM AUTHOR]

The article reports on finding all subgraphs of an undirected graph [H]. A maximal complete subgraph is also called clique which refers to a complete subgraph that is not included in any other complete subgraph. According to the authors, a research paper was released wherein descriptions of techniques to find maximal complete subgraphs are provided. The authors discussed two algorithms using a branch-and-bound technique so that there will be no clique. The first algorithm produces cliques in lexicographic order while the second is derived from the first algorithm.

Describes a computer program for the implementation of graph algorithms which wins Shannon Switching Games. Difference in the goals between players of the game; Existence of a winning strategy between players; Effect of ease of communication between players on computer program demonstration.

This paper presents the scheduling algorithm used in the Computer Assisted Registration System at the University of Tennessee. Notation is defined and the logic of the algorithm necessary to implement educational policy is described. Results from the first term's implementation are presented. [ABSTRACT FROM AUTHOR]

The utilization of storage is studied in a two-level memory hierarchy. The first storage level, which is the fast store, is divided into a number of storage areas. When an entry is to be filed in the hierarchy, a hashing algorithm will attempt to place the entry into one of these areas. If this particular area is full, then the entry will be placed into the slower second-level store, even though other areas in the first-level store may have space available. Given that N entries have been filed in the entire hierarchy, an expression is derived for the expected number of entries filed in the first-level store. This expression gives a measure of how effectively the first-level store is being used. By means of examples, storage utilization is then studied as a function of the hashing algorithm, the number of storage areas into which the first-level store is divided and the total size of the first-level store. [ABSTRACT FROM AUTHOR]

Given the horizontal and vertical projections of a finite binary pattern f, can we reconstruct the original pattern f? In this paper we give a characterization of patterns that ore reconstructable from their projections. Three algorithms ore developed to reconstruct both unambiguous and ambiguous patterns, it is shown that an unambiguous pattern can be perfectly reconstructed in time m × n and that a pattern similar to an ambiguous pattern can also be constructed in time m × n, where m, n are the dimensions of the pattern frame. [ABSTRACT FROM AUTHOR]

This section provides summaries of papers on algorithms. The paper "Function Minimization and Linear Search," by K. Fielding discusses a procedure that minimizes a function using the method of Broyden. The parameters of the procedure include iterations, maxiters, and tolerance. In his paper "Binary Ordered Walsh Functions," H. Hübner explains the procedure binwal which computes the binary ordered Walsh function. The paper "Simpson's Rule for Multiple Integration" states that an algorithm can be marginally improved by replacing each integer constant to its equivalent decimal number.

Multiprogramming as it is discussed here is a mode of computer operation in which two or more programs are concurrently in processor memory and proceeding, each using the same central processor unit (CPU) and input-output (I/O) channels. These programs are actually proceeding intermittently and singly, according to eligibility (readiness to proceed) and priority. It is useful to be able to represent them as proceeding continuously and simultaneously, each at an effective rate, which may be a fraction of that which it would enjoy in the absence of the other programs. The effective progress rate of each program is sensitive to many detailed characteristics of itself and its co-residents; and simulation has been the best available method of predicting it. This paper presents the results of progress in developing an alternative to simulation, a simulation-tested iterative computation of these rates under certain situations. The algorithm is sensitive to most of the factors that control the phenomenon, including nonquantitative or topological features of the programs' structures. [ABSTRACT FROM AUTHOR]

This paper is concerned with a review and examination of several existing algorithms for the zero-one programming problem. Computational experience is summarized. The machine time and storage requirements of several of the algorithms are compared over several test problems of small and intermediate size. Computer experiments still provide little hope of solving problems with over 100 variables with a reasonable amount of machine time. [ABSTRACT FROM AUTHOR]

The use of decision tables as a tool in systems analysis and for program specification is now becoming accepted. Rules on redundancy, contradiction, and completeness for limited entry tables were published in 1963. These ore usually used for checking, preceded if necessary by a conversion from extended to limited entry form. Processors which automatically translate tables to more conventional program usually base their diagnostic facilities on these rules. In this paper it is suggested that these rules ore unsatisfactory and that the important aspect of checking is to eliminate ambiguity from tables. Ambiguity is defined and discussed, and a procedure for producing checked out decision tables is proposed. The theoretical basis of the algorithm used is established. The importance of well-designed diagnostic facilities in decision table processors is emphasized. [ABSTRACT FROM AUTHOR]

For the segmentation of a program it is useful to have a reasonable estimation of the values of Sij, where Sij is the mean value of the number of jumps from the ith instruction on to the ith instruction in the run time. In the cases where the Sij, are estimated directly, the structure of the whole program must be generally taken into account; therefore it is very difficult for the programmer and/or the translator to obtain a good estimation of the Sij. It is easier to estimate not Sij, but the quantities pij = Sij·ci,/∑jN=1 Sij, where c, is an arbitrary positive constant for each i. Although the pij are, for each i, proportional to Sij, the estimation of pij is easier, because we must estimate only the "probabilities" of events where instruction lj, is executed after instruction li. This estimation can often be done without considering the structure of the whole program. In the first part of the paper, using the theory of the Markov chains, an algorithm for the computation of the Sij from the p , is found, and some ways of obtaining estimates of the pij are given. In the second part a variant of this algorithm is derived, avoiding the necessity of computation involving large matrices. [ABSTRACT FROM AUTHOR]

Presents an implementation of Stiefel's exchange algorithm for determining a Chebyshev solution to an overdetermined system of linear equations. Use of Gaussian LU decomposition with row interchanges; Stability of implementation than those usually given in the literature; Generalization of Stiefel's algorithm which permits the occasional exchange of two equations simultaneously.

A method for returning registers to the free list is an essential part of any list processing system. In this paper, past solutions of the recovery problem are reviewed and compared. A new algorithm is presented which offers significant advantages of speed and storage utilization. The routine for implementing this algorithm can be written in the list language with which it is to be used, thus insuring a degree of machine independence. Finally, the application of the algorithm to a number of different list structures appearing in the literature is indicated. [ABSTRACT FROM AUTHOR]

Neely has discussed computational error generated by some algorithms used to compute various statistics. In the present paper methods are described which are error-free, simple in concept, and usually less costly in machine time than those mentioned by Neely. [ABSTRACT FROM AUTHOR]

Nonlinear least squares problems frequently arise for which the variables to be solved for can be separated into a linear and a nonlinear part. A variable projection algorithm has been developed recently which is designed to take advantage of the structure of a problem whose variables separate in this way. This paper gives a slightly more efficient and slightly more general version of this algorithm than has appeared earlier. [ABSTRACT FROM AUTHOR]

Presents the author's comments on the paper "A Multiple-Precision Division Algorithm," by C.J. Mifsud, published in the November 1970 issue of the journal "Communications of the ACM." Account of difficulties that arises with the programming and implementation of the algorithm described in the paper; Avoidance of the possibility of overflow in the calculation of trial cipher; Solution to the problems the algorithm described in the paper; Suggestions for additional informative statements that should be inserted in the original algorithm.

High-priority paralysis is the degradation that can occur in multiprogramming systems when scheduling is based primarily on preassigned priorities. It can be alleviated by modifying the scheduling algorithm to maximize the number of programs active at one time. The case history given in this paper indicates two general methods by which simultaneity can be increased. Possible refinements in the scheduling algorithm for future improvements are considered briefly. [ABSTRACT FROM AUTHOR]

This paper describes an alternate method for summing a set of floating-point numbers. Comparison of the error bound for this method with that of the standard summation method shows that it is considerably less sensitive to propagation of round-off error. [ABSTRACT FROM AUTHOR]

The article discusses the computation of rational approximations using existing algorithms. In a recent paper it is shown that minimax logarithmic approximations are optimal for square root calculations, making the minimax logarithmic problem of practical interest. The authors point out how rational approximations which are best with respect to maximum logarithmic error can be computed by existing algorithms. Suppose one wishes to approximate a positive continuous function "f" by a positive rational function R, then the logarithmic error at a point x is log (f(x))-- log (R(x)). The approximation problem is thus equivalent to ordinary approximation of continuous function g = log (f) by log {R).

Features the background and algorithms for masking the rotational latency of a disk or drum. Discussion of the anticipatory input and output of data to buffer and primary memories for a monoprogrammed computer system; Presentation of a basic permutation algorithm.

An integration technique for the automatic solution of an initial value problem for a set of ordinary differential equations is described. A criterion for the selection of the order of approximation is proposed. The objective of the criterion is to increase the step size so as to reduce solution time. An option permits the solution of "stiff" differential equations. A program embodying the techniques discussed appears in Algorithm 407. [ABSTRACT FROM AUTHOR]

Pollack has proposed on algorithm for converting decision tables into flowcharts which minimize subsequent execution time when compiled into a computer program. Two modifications a this algorithm are proposed. The first relies on Shannon's noiseless coding theorem and the communications concept of entropy but does not completely test the ELSE Rule. The second modification completely tests the ELSE Rule but results in more executions than the first modification. Both modifications result in lower execution time than Pollack's algorithm. However, neither modification guarantees a globally optimal solution. [ABSTRACT FROM AUTHOR]

An algorithm for Filon quadrature is described. Considerable attention has been devoted to an analysis of the round-off and truncation errors. The algorithm includes an automatic error control feature. [ABSTRACT FROM AUTHOR]

Under the assumption that a processor may have a multiplicity of arithmetic units, a compiler for such a processor should produce object code to take advantage of possible parallelism of operation. Most of the presently known compilation techniques are inadequate for such a processor because they produce expression structures that must be evaluated serially. A technique is presented here for compiling arithmetic expressions into structures that can be evaluated with a high degree of parallelism. The algorithm is a variant of the so-called "top-down" analysis technique, and requires only one pass of the input text. [ABSTRACT FROM AUTHOR]

A brief description is given of the implementation technique for the replacement rule of the AMBIT programming language. The algorithm for the "AMBIT scan" and an example of its application are given. The algorithm is applicable to other members of the family of string transformation languages of which AMBIT is a member, and it provides a rationale for the design of the AMBIT language. [ABSTRACT FROM AUTHOR]

A survey of machines which are more powerful than finite automata and less powerful than general Turing machines is presented. It is felt that the machines in this category are as closely related to digital computers as either the finite automata or the unrestricted Turing machines. Intermediate machines can be created by adjoining an infinite-state memory to a finite-state machine and then performing any or all of the following: (1) restrict the manner in which the unbounded portion of the memory can be accessed, (2) bound the number of steps allowed for a computation by some increasing recursive function of the length of the input, (3) restrict the total amount of memory available in the same manner. Examples from all three classes and their properties are discussed. [ABSTRACT FROM AUTHOR]

The article focuses on key-to-address transformation techniques and the results of a performance study on large existing formatted files. The experimental results comparing six commonly used key-to-address transformation techniques were presented by the researchers. One transformation in the study referred to as "generalized radix transformation method" is an elaborate technique based on radix transformation. This method of transformation consists of a radix transformation algorithm as well as hardware implementation to carry out the steps of this transformation in an efficient manner. The intricacy of the generalized radix transformation method has motivated researchers to conduct further studies of the technique. The additional results are presented after a brief description of the basic algorithm used in this generalized radix transformation method. Additional experiments on the files showed that the distribution of the keys was particularly sensitive to the arbitrary selection of an 8-bit grouping.

The article provides an analysis of key-to-address transformation techniques and the results of a performance study on large existing formatted files. The experimental results comparing six commonly used key-to-address transformation techniques were presented by the researchers. One transformation in the study referred to as "generalized radix transformation method" is an elaborate technique based on radix transformation. This method of transformation consists of a radix transformation algorithm as well as hardware implementation to carry out the steps of this transformation in an efficient manner. The intricacy of the generalized radix transformation method has motivated researchers to conduct further studies of the technique. The additional results are presented after a brief description of the basic algorithm used in this generalized radix transformation method. Additional experiments on the files showed that the distribution of the keys was particularly sensitive to the arbitrary selection of an 8-bit grouping.

The purpose of this note is to report computational experience additional to that recently summarized by Gue et al., with two algorithms for the zero-one linear programming problem. An error in Gue's paper is corrected. The utility of one of the algorithms as a suboptimizer is indicated. [ABSTRACT FROM AUTHOR]