Sign In

Communications of the ACM

Table of Contents


A letter from the ACM vice-president: two messages


Forum


The programmer as navigator

This year the whole world celebrates the five-hundredth birthday of Nicolaus Copernicus, the famous Polish astronomer and mathematician. In 1543, Copernicus published his book, Concerning the Revolutions of Celestial Spheres, …

Dynamic verification of operating system decisions

Dynamic verification of a decision implies that every time the decision is made there is a consistency check performed on the decision using independent hardware and software. The dynamic verification of operating system decisions …

A parser-generating system for constructing compressed compilers

This paper describes a parser-generating system (PGS) currently in use on the CDC-6500 computer at Purdue University. The PGS is a Fortran-coded program that accepts a translation grammar as input and constructs from it a compact …

A scan conversion algorithm with reduced storage requirements

Most graphics systems using a raster scan output device (CRT or hardcopy) maintain a display file in the XY or random scan format. Scan converters, hardware or software, must be provided to translate the picture description from …

Experiment with an automatic theorem-prover having partial ordering inference rules

Automatic theorem-provers need to be made much more efficient. With this in mind, Slagle has shown how the axioms for partial ordering can be replaced by built-in inference rules when using a particular theorem-proving algorithm …

Algorithm 464: eigenvalues of a real, symmetric, tridiagonal matrix [F2]

This algorithm uses a rational variant of the QR transformation with explicit shift for the computation of all of the eigenvalues of a real, symmetric, and tridiagonal matrix. Details are described in [1]. Procedures tred1 or …

Algorithm 465: student's t frequency [S14]


Algorithm 466: four combinatorial algorithm [G6]


Algorithm 467: matrix transposition in place [F1]


Algorithm 467: Matrix Transposition in Place


Algorithm 468: algorithm for automatic numerical integration over a finite interval [D1]


Algorithm 469: arithmetic over a finite field [A1]


A note on sub-expression ordering in the execution of arithmetic expressions

A counterexample to the supposed optimality of an algorithm for generating schedules for trees of tasks with unequal execution times is presented. A comparison with the “critical path” heuristic is discussed.

Comment on Brent's scatter storage algorithm

R.P. Brent in his presentation of a modification to the linear quotient algorithm [1] shares the common misconception that dynamic chaining requires larger table entries because of the space required for link fields.

Tree-structured programs

With this note I hope to bridge the gap between the adherents of structured programming and the devotees of the unrestricted goto. I describe a style of programming which combines the advantages of structured programming with …

A recurrence scheme for converting from one orthogonal expansion into another

A generalization of a scheme of Hamming for converting a polynomial Pn(x) into a Chebyshev series is combined with a recurrence scheme of Clenshaw for summing any finite series whose terms satisfy a three-term recurrence formula …

An algorithm for the approximate solution of Wiener-Hopf integral equations

An explicit approximate solution ƒ(h)&agr; is given for the equation ƒ(t) = ∫0 k(t - &tgr;)ƒ(&tgr;) d&tgr; + g(t), t > 0, (*) where k, gL1(- ∞, ∞) ∩ L2(-∞, ∞), and where it is assumed that the classical Wiener-Hopf technique may be applied …

Solving the biharmonic equation in a square: a direct versus a semidirect method

Two methods for solving the biharmonic equation are compared. One method is direct, using eigenvalue-eigenvector decomposition. The other method is iterative, solving a Poisson equation directly at each iteration.

Computers, society, and law—the role of legal education