May 1981 - Vol. 24 No. 5

May 1981 issue cover image

Features

Research and Advances

The external auditor’s review of computer controls

The Foreign Corrupt Practices Act of 1977, coupled with growing demands for corporate accountability, have forced both auditors and computer administrators to evaluate computer based controls. Computer administrators can benefit from both a knowledge of an auditor's approaches to evaluating controls and his/her recommendations for control improvements. Here, a survey of the control evaluation practices and desirable control features identified by computer auditors is presented, along with recommendations to ease the burden of the auditor's review. The authors' suggestions should ease the tasks of internal control analysis and of preparation for possible public reports on an organization's system of internal control.
Research and Advances

Another spelling correction program

We read James L. Peterson's article, “Computer Programs for Detecting and Correcting Spelling Errors” with great interest. We too have recently developed a spelling correction program as part of a tutorial on programming techniques and style. Our basic modesty inhibited us from publishing the details—there was, after all, little research involved in making the program. However, on reflection, there are several features in our design that we feel merit wider circulation.
Research and Advances

Experience with a space efficient way to store a dictionary

The paper, “Computer Programs for Detecting and Correcting Spelling Errors” by James L. Peterson [3], listed methods for checking and correcting spelling errors. One significant method, however, was not included: a probabilistic technique suggested by Carter, Floyd, Gill, Markovsky, and Wegman [1]. The present note discusses aspects of these practical space efficient algorithms for testing set membership—a simple abstraction of looking a word up in a dictionary. An implementation of one of these algorithms uses only 20 percent of the space used by the Stanford SPELL program described by Peterson.
Research and Advances

Updating a master file—yet one more time

For several years I have been teaching a file updating algorithm which is essentially the same as that in Dwyer's admirable paper [1]. There is one unjustified objection to the algorithm that perceptive students and people with batch processing experience almost invariably raise and which is not addressed by Dwyer. The objection is based on a situation which arises in a batch processing environment with several users, where key-ordered sequential update is used.
Research and Advances

The cube-connected cycles: a versatile network for parallel computation

An interconnection pattern of processing elements, the cube-connected cycles (CCC), is introduced which can be used as a general purpose parallel processor. Because its design complies with present technological constraints, the CCC can also be used in the layout of many specialized large scale integrated circuits (VLSI). By combining the principles of parallelism and pipelining, the CCC can emulate the cube-connected machine and the shuffle-exchange network with no significant degradation of performance but with a more compact structure. We describe in detail how to program the CCC for efficiently solving a large class of problems that include Fast Fourier transform, sorting, permutations, and derived algorithms.
Research and Advances

Strip trees: a hierarchical representation for curves

The use of curves to represent two-dimensional structures is an important part of many scientific investigations. For example, geographers use curves extensively to represent map features such as contour lines, roads, and rivers. Circuit layout designers use curves to specify the wiring between circuits. Because of the very large amount of data involved and the need to perform operations on this data efficiently, the representation of such curves is a crucial issue. A hierarchical representation consisting of binary trees with a special datum at each node is described. This datum is called a strip and the tree that contains such data is called a strip tree. Lower levels in the tree correspond to finer resolution representations of the curve. The strip tree structure is a direct consequence of using a special method for digitizing lines and retaining all intermediate steps. This gives several desirable properties. For curves that are well-behaved, intersection and point-membership (for closed curves) calculations can be solved in 0(log n) where n is the number of points describing the curve. The curves can be efficiently encoded and displayed at various resolutions. The representation is closed under intersection and union and these operations can be carried out at different resolutions. All these properties depend on the hierarchical tree structure which allows primitive operations to be performed at the lowest possible resolution with great computational time savings. Strip trees is a linear interpolation scheme which realizes an important space savings by not representing all the points explicitly. This means that even when the overhead of the tree indexing is added, the storage requirement is comparable to raster representations which do represent most of the points explicitly.

Recent Issues

  1. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  2. September 2024 CACM cover
    September 2024 Vol. 67 No. 9
  3. August 2024 CACM cover
    August 2024 Vol. 67 No. 8
  4. July 2024 CACM cover
    July 2024 Vol. 67 No. 7