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 Equipment Corporation; Bernard A. Galler, University of Michigan; Patricia Goldberg, IBM Corporation; John Hamblen, University of Missouri at Rolla; Elliot Pinson, Bell Telephone Laboratories; and Ivan Sutherland, California Institute of Technology. Also participating in the workshop were representatives of NSF and other government agencies. In addition to the authors, a number of other people have contributed to the contents of this report. In preparation for the original workshop, all doctorate-granting computer science departments in the nation were asked for comments and suggestions on the problems of experimental computer science. A version of the current report dated January 15 was circulated to these departments and to a number of industrial and government groups for criticism. The editors and authors of this final version gratefully acknowledge the contribution of a large number of other people at all stages in the preparation of the report. [Note: Following this presentation of the report, there is a position paper on the crisis in experimental computer science written by the ACM Executive Committee.]
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 over the best previously known insertion algorithms of Hirschberg and Kosaraju, which require time O(log2n). Moreover, the O(log n) complexity is optimal.
Earlier results have shown that deletion in such a structure can also be performed in O(log n) time. Thus the result of this paper gives a negative answer to the question of whether such trees should be the first examples of their kind, where deletion has a smaller time complexity than insertion. Furthermore, it can now be concluded that insertion, deletion, and retrieval in OSHB trees can be performed in the same time as the corresponding operations for the more general AVL trees, to within a constant factor. However, the insertion and deletion algorithms for OSHB trees appear much more complicated than the corresponding algorithms for AVL trees.
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 important in certain areas of database implementation in which there are constraints on the permissible sequences of actions.
Two PAD algorithms are presented; one uses a simple path matrix representation and the other uses a list with an “artificial gradient.” Experiments suggest that for large N the second is considerably faster, though both are asymptotically O(NR), where N is the number of nodes and R is the expected number of nodes reachable along paths from any given node.
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 data structure, where class labels identify the regions bordering each segment on either side. The approximation algorithm presented operates on such an organization, eliminating the need for the recognition of region boundaries. Each segment is examined only once. The versatility of the new organization is further illustrated by the outline of algorithms for area computation and point inclusion. The algorithm is applied to a set of soil maps converted to computer-readable form by means of a coordinate digitizer.
reachable along paths from any given node.
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 specifically intended for automatic computation. Our discussion is expository, with emphasis on reaching a suitable definition of “accuracy.” Each of the four algorithms is analyzed for the conditions under which it will be accurate. We conclude that all four algorithms will provide accurate answers for many problems, but two of the algorithms, one new, one old, are substantially more accurate on difficult problems than are the other two.
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 as the best existing updating method.
