December 1971 - Vol. 14 No. 12
Features
Reconstruction of pictures from their projections
There are situations in the natural sciences and medicine (e.g. in electron microscopy and X-ray photography) in which it is desirable to estimate the gray levels of a digital picture at the individual points from the sums of the gray levels along straight lines (projections) at a few angles. Usually, in such situations, the picture is far from determined and the problem is to find the “most representative” picture. Three algorithms are described (all using Monte Carlo methods) which were designed to solve this problem. The algorithms are applicable in a large and varied number of fields. The most important uses may be the reconstruction of possibly asymmetric particles from electron micrographs and three-dimensional X-ray analysis.
Algorithmic selection of the best method for compressing map data strings
The best of a dozen different methods for compressing map data is illustrated. The choices are generated by encoding data strings—sequence of like codes—by three methods and in four directions. Relationships are developed between compression alternatives to avoid comparing all of them. The technique has been used to compress data from forest resource maps, but is widely applicable to map and photographic data reduction.
Retrieval—Update speed tradeoffs using combined indices
In a paper in the November 1970 Communications of the ACM, V.Y. Lum introduced a technique of file indexing named combined indices. This technique permitted decreased retrieval time at the cost of increased storage space. This paper examines combined indices under conditions of file usage with different fractions of retrieval and update. Tradeoff curves are developed to show minimal cost of file usage by grouping various partially combined indices.
Implementation of the substring test by hashing
In a paper in the November 1970 Communications of the ACM, V.Y. Lum introduced a technique of file indexing named combined indices. This technique permitted decreased retrieval time at the cost of increased storage space. This paper examines combined indices under conditions of file usage with different fractions of retrieval and update. Tradeoff curves are developed to show minimal cost of file usage by grouping various partially combined indices.
BLISS: a language for systems programming
A language, BLISS, is described. This language is designed so as to be especially suitable for use in writing production software systems for a specific machine (the PDP-10): compilers, operating systems, etc. Prime design goals of the design are the ability to produce highly efficient object code, to allow access to all relevant hardware features of the host machine, and to provide a rational means by which to cope with the evolutionary nature of systems programs. A major feature which contributes to the realization of these goals is a mechanism permitting the definition of the representation of all data structures in terms of the access algorithm for elements of the structure.
New LISP techniques for a paging environment
The system described herein employs the block concept, and that of global and local variables, in addition to the methods applied in most LISP systems. Also, a new means of list representation is used: “local sequential” for lists created during compilation, and “block level sequential” for those created dynamically. A new garbage collection algorithm has been introduced to make lists as compact as possible; partial garbage collection is performed after each block exit instead of total garbage collection when storage is exhausted. The algorithm does not use the customary flagging procedure. This combination of features has eliminated the need for a free list, and effectively minimizes the number of pages used at any moment.
A note on “A modification of Nordsieck’s method using an ‘Off-Step’ point”
An examination was made of the experimental results presented by J.J. Kohfeld and G.T. Thompson [1] in their paper on a modification of Nordsieck's method for the numerical solution of ordinary differential equations, using a multiple precision arithmetic package [2] available on the IBM 7094 at The Ohio State University Computer Center. A comparison was made between the errors of the Nordsieck and the Gragg-Stetter-Nordsieck methods in which, after the starting procedure, the interval length “h” was held constant. Results relative to the five functions used by Kohfeld and Thompson are presented in Tables I and II (@ b means 10b).
Rapid computation of general interpolation formulas and mechanical quadrature rules
Let ƒ have n continuous derivatives on a closed interval [a, b] and let L be a linear functional. The attempt is made to approximate L(ƒ) with L(Q) where Q is a polynomial, approximating ƒ. Algorithms are developed for rapid computation of L(Q) for a wide class of selections of Q which includes the Lagrangian and Hermitian rules as special cases.
An extension of the Munkres algorithm for the assignment problem to rectangular matrices
The assignment problem, together with Munkres proposed algorithm for its solution in square matrices, is presented first. Then the authors develop an extension of this algorithm which permits a solution for rectangular matrices.
Timing results obtained by using an adapted version of Silver's Algol procedure are discussed, and a relation between solution time and problem size is given.
Algorithm 415: Algorithm for the assignment problem (rectangular matrices)
This algorithm is a companion to [3] where the theoretical background is described.
Algorithm 416: Rapid computation of coefficients of interpolation formulas
This algorithm is a companion to [1] where the theoretical background is described
Algorithm 417: Rapid computation of weights of interpolatory quadrature rules
This algorithm is a companion to [1] where the theoretical background is described
