Sign In

Communications of the ACM

Table of Contents


ACM President's Letter: ethics


Syntax-directed least-errors analysis for context-free languages: a practical approach

A least-errors recognizer is developed informally using the well-known recognizer of Earley, along with elements of Bellman's dynamic programming. The analyzer takes a general class of context-free grammars as drivers, and any …

A fast method for solving a class of tridiagonal linear systems

The solution of linear systems having real, symmetric, diagonally dominant, tridiagonal coefficient matrices with constant diagonals is considered. It is proved that the diagonals of the LU decomposition of the coefficient matrix …

A method of bivariate interpolation and smooth surface fitting based on local procedures

A method is designed for interpolating values given at points of a rectangular grid in a plane by a smooth bivariate function z = z(x, y). The interpolating function is a bicubic polynomial in each cell of the rectangular grid …

Tridiagonalization by permutations

Tridiagonalizing a matrix by similarity transformations is an important computational tool in numerical linear algebra. Consider the class of sparse matrices which can be tridiagonalized using only row and corresponding column …

Computation of Legendre series coefficients

LEGSER approximates the first N + 1 coefficients Bn of the Legendre series expansion of a function ƒ(x) having known Chebyshev series coefficients An. Several algorithms are available for the computation of coefficients An of …

Bivariate interpolation and smooth surface fitting based on local procedures


Reentrant polygon clipping

A new family of clipping algorithms is described. These algorithms are able to clip polygons against irregular convex plane-faced volumes in three dimensions, removing the parts of the polygon which lie outside the volume. In …

Comments on the algorithms of Verhelst for the conversion of limited-entry decision tables to flowcharts

In his interesting contribution to the study of the conversion of limited-entry decision tables to flowcharts or sequential testing procedures, Verhelst [1] presents two algorithms, one of which is claimed to produce the optimal …

A numbering system for combinations

It is often necessary to generate the sequence of combinations of s things chosen from among n things, or to generate a random member of this sequence. Various algorithms have been given for these tasks. Algorithm 94 [1] is a …

A CRT report generating system