Sign In

Communications of the ACM

Table of Contents


ACM president's letter: ACM and self-assessment


Algorithm 492: Generation of all the cycles of a graph from a set of basic cycles [H]

The PL/I procedure CYCLE_GENERATOR is an implementation of Gibbs' algorithm [1] for finding all the cycles in a graph from a set of basic cycles.

Illumination for computer generated pictures

The quality of computer generated images of three-dimensional scenes depends on the shading technique used to paint the objects on the cathode-ray tube screen. The shading algorithm itself depends in part on the method for modeling …

A cost oriented algorithm for data set allocation in storage hierarchies

Data set allocation in today's multilevel storage systems is usually based on qualitative, ad hoc decisions. While it would be desirable to obtain an optimal solution to this allocation problem, it is clear that the number of …

Significant event simulation

This paper compares a new method of simulation organization, called the significant event method, with an old one, called the clock pulse method, using as examples two automobile traffic models. The significant event method is …

Indirect threaded code

An efficient arrangement for interpretive code is described. It is related to Bell's notion of threaded code but requires less space and is more amenable to machine independent implementations.

A simplified recombination scheme for the Fibonacci buddy system

A simplified recombination scheme for the Fibonacci buddy system which requires neither tables nor repetitive calculations and uses only two additional bits per buffer is presented.

Efficient string matching: an aid to bibliographic search

This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords …

A linear space algorithm for computing maximal common subsequences

The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space. An algorithm is presented which will solve this problem in quadratic time and in linear space.

Addition in an arbitrary base without radix conversion

hnique; using it, one may add and subtract numbers represented in any radix, including a mixed radix, and stored one digit per byte in bytes of sufficient size. Radix conversion is unnecessary, no looping is required, and numbers …

Sorting X + Y


Improved event-scanning mechanisms for discrete event simulation

Simulation models of large, complex “real-world” applications have occasionally earned the reputation of eating up hours of computer time. This problem may be attributed in part to difficulties such as slow stochastic convergence …

ACM Forum