November 1968 - Vol. 11 No. 11
Features
Automata, formal languages abstract switching, and computability in a Ph.D. computer science program
A number of courses are listed in the area described as automata, formal languages, abstract switching, and computability, that might be available to a Ph.D. student in computer science. A brief catalog description of each course is supplied and the role of each of the courses in the graduate program is discussed.
Storage organization in programming systems
The system of program and data representation that has been in use on the Rice University computer for five years is described. Each logical entity in storage occupies a block of consecutive memory locations. Each block is labeled by a codeword and may contain a program, a data vector, or codewords which in turn label blocks to form arrays. This storage arrangement is discussed with its realized advantages in programming systems: simplicity of programmed addressing, flexibility of data structures, efficiency of memory utilization, variability of system composition during execution, means of linkage between programs and from programs to data, and basis for storage protection. The application of labeled blocks may be extended to areas of time-sharing and multi-media storage control. On the basis of experience at Rice, some ideas on such extensions are presented.
Extensive software problems confront an organization which possesses a number of different computers and which frequently acquire new ones. To maintain cohesion, a system must be developed, written in a high level language, which minimizes machine dependencies and isolates those which are necessary. A language and a compiler for that language are discussed here.
The language, called LRLTRAN, is a heavily augmented FORTRAN. The three-pass compiler makes use internally of a postfix Polish notation (pass I to pass II) and a free representation referred to as a “composite blocking table” (pass I to pass III). Machine-independent optimization occurs in pass II and DO-loop and machine-dependent optimization in pass III.
A note on a relevance estimate and its improvement
In this paper the effect of iterating the improvement procedure is examined. It is shown that applications of the improvement factor beyond the first time are ineffectual, and that the factor is but a scale factor.
One-line random number generators and their use in combinations
Some one-line random number generators, i.e. generators requiring a single FORTRAN instruction are discussed, and some short FORTRAN programs which mix several such generators are described. The aim is to provide methods for incorporating random number generators directly in FORTRAN programs, by means of a few in-line instructions. The advantages are speed (avoiding linkage to and from a subroutine), convenience, and versatility. Anyone wishing to experiment with generators, either using congruential generators by themselves or mixing several generators to provide a composite with potentially better statistical properties than the library generators currently available, may wish to consider some of the simple FORTRAN programs discussed here.
Approximate solution of initial-boundary wave equation problems by boundary-value techniques
A new boundary-value technique is proposed for the treatment of initial-boundary-value problems for linear and mildly non-linear wave equations. Several illustrative examples are offered to demonstrate the ease with which the method can be applied.
Theoretical and practical values of error coefficients useful in bounding the error in integrating periodic analytic functions with the trapezoidal rule are tabulated for various ranges of the parameters.
Theoretical and practical values of error coefficients useful in bounding the error in integrating periodic analytic functions with the trapezoidal rule are tabulated for various ranges of the parameters.
Algorithms: Algorithm 338: algol procedures for the fast Fourier transform
The following procedures are based on the Cooley-Tukey algorithm [1] for computing the finite Fourier transform of a complex data vector; the dimension of the data vector is assumed here to be a power of two. Procedure COMPLEXTRANSFORM computes either the complex Fourier transform or its inverse. Procedure REALTRANSFORM computes either the Fourier coefficients of a sequence of real data points or evaluates a Fourier series with given cosine and sine coefficients. The number of arithmetic operations for either procedure is proportional to n log2 n, where n is the number of data points.
Correspondences of 8-bit and Hollerith codes for computer environments—a USASI tutorial
The correspondence tables in the document reflect USASCII standard code assignments as well as other codes. Comments that refer to the assignments of characters or character sets in columns 8 through 15 of Table 1 as a basis for standardization are solicited.
