March 1975 - Vol. 18 No. 3
Features
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 the complete timetabling process; to use a more compact data representation and more efficient processing techniques; to take fuller advantage of possible available previous knowledge about the matrix. And it is designed as a structured program, which can readily be coded by the reader in the high level or low level programming language of his choice. Practical tests of the method have shown it to be a good basis for a realistic timetabling algorithm.
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 neither mathematics nor typesetting. Experience indicates that the language can be learned in an hour or so, for it has few rules and fewer exceptions. For typical expressions, the size and font changes, positioning, line drawing, and the like necessary to print according to mathematical conventions are all done automatically. For example, the input sum from i=0 to infinity x sub i = pi over 2 produces ∑∞i=0xi = &pgr;/2
The syntax of the language is specified by a small context-free grammar; a compiler-compiler is used to make a compiler that translates this language into typesetting commands. Output may be produced on either a phototypesetter or on a terminal with forward and reverse half-line motions. The system interfaces directly with text formatting programs, so mixtures of text and mathematics may be handled simply.
This paper was typeset by the authors using the system described.
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 of his algorithm in terms of 64-word vectors.
This paper describes the characteristics, goals, and philosophy of the language, and discusses some of the problems associated with parallel computer architectures.
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 lower bound within 9 percent of the above formula is also derived.
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 is thus functionally equivalent to Hoare's algorithm FIND [1], it is significantly faster on the average due to the effective use of sampling to determine the element T about which to partition X. The average time over 25 trials required by SELECT and FIND to determine the median of n elements was found experimentally to be: n 500 1000 5000 10000 SELECT 89 ms. 141 ms. 493 ms. 877 ms. FIND 104 ms. 197 ms. 1029 ms. 1964 ms. The arbitrary constants 600, .5, and .5 appearing in the algorithm minimize execution time on the particular machine used. SELECT has been shown to run in time asymptotically proportional to N + min (I, N-I), where N = L - R + 1 and I = K - L + 1. A lower bound on the running time within 9 percent of this value has also been proved [2]. Sites [3] has proved SELECT terminates.
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 index sequential organization. The purpose of this study is to propose and analyze a file organization method which should be appropriate for the same type of environment as index sequential but would be more efficient at the two types of access. This proposed method is designated the Algorithm Sequential Access Method (ASAM).
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 standard X3.9-1966 as their authority.
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 computational costs are developed; and some general comments on application and stability are made.
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 performance is explained.
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 of Patil's proof shows that he has established this claim only under strong restrictions on the use of P and V. These restrictions eliminate programming techniques used by Dijkstra and others since the first introduction of the semaphore concept. This paper contains a solution to the problem. It also discusses the need for the generalized operators suggested by Patil.
