June 1973 Table of Contents | Communications of the ACM

advertisement

Home → Magazine Archive → June 1973 (Vol. 16, No. 6)

Table of Contents

ACM president's letter: whither ACM?

Anthony Ralston

Page 335

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 …

R. G. Hamlet

Pages 337-343

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 …

Erol Gelenbe, J. C. A. Boekhorst, J. L. W. Kessels

Pages 343-349

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 …

J. Carver Hill

Pages 350-351

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 …

Harold S. Stone, Samuel H. Fuller

Pages 352-353

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

Peter F. Stockhausen

Pages 353-354

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 …

Robert L. Ling

Pages 355-361

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 …

Ben Shneiderman

Pages 362-365

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 …

Horst Strunz

Pages 366-369

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 …

James R. Bell

Pages 370-372

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 …

John Hopcroft, Robert Tarjan

Pages 372-378

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 …

Terry Beyer, D. F. Swinehart

Page 379

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.

J. Ferguson, P. A. Staley

Pages 380-382

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 …

W. D. Hoskins

Pages 382-385

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 …

Franz L. Alt, Judith Yuni Kirk

Pages 386-391