September 1979 - Vol. 22 No. 9
Features
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…
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…
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…
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…
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…
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…
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…
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…