Sign In

Communications of the ACM

Table of Contents


ACM president's letter: whither ACM?


Efficient multiprogramming resource allocation and accounting

Although sometimes thought of as only a component of time-sharing operation, multiprogramming can involve broader questions of resource allocation, since fairness is not required to meet a response criterion. In a multiprogrammed …

Minimizing wasted space in partitioned segmentation

A paged virtual memory system using a finite number of page sizes is considered. Two algorithms for assigning pages to segments are discussed. Both of these algorithms are simple to implement. The problem of choosing the page …

Synchronizing processors with memory-content-generated interrupts

Implementations of the “Lock-Unlock” method of synchronizing processors in a multiprocessor system usually require uninterruptable, memory-pause type instructions. An interlock scheme called read-interlock, which does not require …

On the near-optimality of the shortest-latency-time-first drum scheduling discipline

For computer systems in which it is practical to determine the instantaneous drum position, a popular discipline for determining the sequence in which the records are to be accessed is the so-called shortest-latency-time-first …

Adapting optimal code generation for arithmetic expressions to the instruction sets available on present-day computers


A computer generated aid for cluster analysis

A computer generated graphic method, which can be used in conjunction with any hierarchical scheme of cluster analysis, is described and illustrated. The graphic principle used is the representation of the elements of a data  …

Optimum data base reorganization points

In certain data base organization schemes the cost per access may increase due to structural inefficiencies caused by update. By reorganizing the data base the cost per access may be reduced. However, the high cost of a reorganization …

The development of decision tables via parsing of complex decision situations

A new parsing technique is proposed which allows parsing based only on syntactical characteristics of the decision problem. It requires a description of the problem in decision grid chart format and allows the development of  …

Threaded code

The concept of “threaded code” is presented as an alternative to machine language code. Hardware and software realizations of it are given. In software it is realized as interpretive code not needing an interpreter. Extensions …

Algorithm 447: efficient algorithms for graph manipulation

Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths of iterative and each iteration produces …

Algorithm 448: number of multiply-restricted partitions

Given a positiver integer m and an ordered k-tuple c = (c1, ··· , ck) of not necessarily distinct positive integers, then any ordered k-tuple s = (s1, ··· , sk) of nonnegative integers such that m = ∑ki-1 sici is said to be a …

Least squares piecewise cubic curve fitting

The matrices involved in a linear least squares formulation are determined for the problem of fitting piecewise cubic functions, those possessing a continuous derivative, to arrays of planar data.

Cubic spline solutions to fourth-order boundary value problems

The cubic spline approximation to the fourth-order differential equation yi&ugr; + p(x)y″ + q(x)y′ + r(x)y = t(x) is shown to reduce to the solution of a five-term recurrence relationship. For some special cases the approximation …

Computer photocomposition of technical text

In computer assisted typesetting by means of photocomposition, special problems arise in highly technical material such as mathematical formulas. New solutions to several of these problems have been devised in the information …