Sign In

Communications of the ACM

Table of Contents

Publication delays

Rejuvenating experimental computer science: a report to the National Science Foundation and others

This report is based on the results of an NSF sponsored workshop held in Washington, D.C. on November 2, 1978. The co-authors of the report are: Gordon Bell, Digital Equipment Corporation; Bernard A. Galler, University of Michigan …

An ACM executive committee position on the crisis in experimental computer science

The following is the text of a letter commenting on the Feldman Report sent to Dr. Richard C. Atkinson, Director of the National Science Foundation, and other Administration and Congressional officials.

On improving the worst case running time of the Boyer-Moore string matching algorithm

It is shown how to modify the Boyer-Moore string matching algorithm so that its worst case running time is linear even when multiple occurrences of the pattern are present in the text.

An optimal insertion algorithm for one-sided height-balanced binary search trees

An algorithm for inserting an element into a one-sided height-balanced (OSHB) binary search tree is presented. The algorithm operates in time O(log n), where n is the number of nodes in the tree. This represents an improvement …

Approximation of polygonal maps by cellular maps

The approximation of polygonal thematic maps by cellular maps, an important operation in geographical data processing, is analyzed. The data organization used for representing the polygonal maps is a widely used segment-based …

Computing standard deviations: accuracy

Four algorithms for the numerical computation of the standard deviation of (unweighted) sampled data are analyzed. Two of the algorithms are well-known in the statistical and computational literature; the other two are new algorithms …

Updating mean and variance estimates: an improved method

A method of improved efficiency is given for updating the mean and variance of weighted sampled data when an additional data value is included in the set. Evidence is presented that the method is stable and at least as accurate …

ACM forum

Progressive acyclic digraphs—a tool for database integrity

A progressive acyclic diagraph (PAD) algorithm accepts are requests and maintains a graph in an acyclic state. When a request creates a cycle, nodes are “detached” until the new arc can be entered acyclically. This process is …