Home → Magazine Archive → March 1975 (Vol. 18, No. 3)
Table of Contents
ACM president's letter: about the refereeing process
Jean E. Sammet
Page 139
Matrix reduction—an efficient method
The paper describes an efficient method for reduction of the binary matrices which arise in some school time-tabling problems. It is a development of that described by John Lions. It has been generalized and adapted to fit into …
H. C. Johnston, C. A. R. Hoare
Pages 141-150
A system for typesetting mathematics
This paper describes the design and implementation of a system for typesetting mathematics. The language has been designed to be easy to learn and to use by people (for example, secretaries and mathematical typists) who know∞ …
Brian W. Kernighan, Lorinda L. Cherry
Pages 151-157
Glypnir—a programming language for Illiac IV
GLYPNIR is one of the earliest existing languages designed for programming the Illiac IV computer. The syntax of the language is based on ALGOL 60, but has been extended to allow the programmer explicitly to specify the parallelism …
D. H. Lawrie, T. Layman, D. Baer, J. M. Randal
Pages 157-164
Expected time bounds for selection
A new selection algorithm is presented which is shown to be very efficient on the average, both theoretically and practically. The number of comparisons used to select the ith smallest of n numbers is n + min(i,n-i) + o(n). A …
Robert W. Floyd, Ronald L. Rivest
Pages 165-172
Algorithm 489: the algorithm SELECT—for finding the ith smallest of n elements [M1]
SELECT will rearrange the values of array segment X[L: R] so that X[K] (for some given K; L ≤ K ≤ R) will contain the (K-L+1)-th smallest value, L ≤ I ≤ K will imply X[I] ≤ X[K], and K ≤ I ≤ R will imply X[I] ≥ X[K. While SELECT …
Robert W. Floyd, Ronald L. Rivest
Page 173
The algorithm sequential access method: an alternative to index sequential
A requirement of many computer file processing systems is the ability to access data stored on a direct access storage device (DASD) both sequentially and randomly. A popular method which provides both types of access is the
…
Jerry D. Whitt, A. Gale Sullenberger
Pages 174-176
A reply to gentleman and Marovich
Gentleman and Marovich in their short communication [Comm. ACM 17, 5 (May 1974) 276-277] make the claim that for FORTRAN “… the language definitions require that subprograms can be separately compiled…,” citing the ANSI FORTRAN …
Richard Alan Karp
Page 174
On computing certain elements of the inverse of a sparse matrix
A recursive algorithm for computing the inverse of a matrix from the LU factors based on relationships in Takahashi, et al., is examined. The formulas for the algorithm are given; the dependency relationships are derived; the …
A. M. Erisman, W. F. Tinney
Pages 177-179
Discrete least squares polynomial fits
The recurrence relation between orthogonal polynomials is widely used for discrete least squares data fitting. A variant of the classical algorithm which has better numerical properties is presented and the reason for its improved …
L. F. Shampine
Pages 179-180
On a solution to the cigarette smoker's problem (without conditional statements)
This report discusses a problem first introduced by Patil, who has claimed that the cigarette smoker's problem cannot be solved using the P and V operations introduced by Dijkstra unless conditional statements are used. An examination …
D. L. Parnas
Pages 181-183
ACM forum
Page 187