May 1969 - Vol. 12 No. 5
Features
An experimental comparison of problem-solving using time-sharing and batch-processing computer systems conducted at MIT is described in this paper. This study is the first known attempt to evaluate two such systems for what may well be the predominant user population within the next decade—the professionals who, as nonprogrammers, are using the computer as an aid in decision-making and problem-solving rather than as a programming end in itself.
Statistically and logically significant results indicate equal cost for usage of the two computer systems; however, a much higher level of performance is attained by time-sharing users. There are indications that significantly lower costs would have resulted if the time-sharing users had stopped work when they reached a performance level equal to that of the batch users. The users' speed of problem-solving and their attitudes made time-sharing the more favorable system.
A note on reliable full-duplex transmission over half-duplex links
A simple procedure for achieving reliable full-duplex transmission over half-duplex links is proposed. The scheme is compared with another of the same type, which has recently been described in the literature. Finally, some comments are made on another group of related transmission procedures which have been shown to be unreliable under some circumstances.
Automated printed circuit routing with a stepping aperture
A computer program for routing interconnections on a two-sided printed circuit board with a regular pattern of lines, pins (terminals), and vias (feed-through holes) is described.
In this program, each interconnection is given a planned routing—typically, down from the upper pin, through a via, and horizontally to the lower pin. From the top, a virtual aperture (i.e. a long horizontal slit) is stepped down the board. The planned routing is the basis for rerouting interconnections within the aperture to resolve conflicts for lines and vias below the aperture and to maximize the effective line usage. If a conflict has not been resolved before the aperture arrives at the lower pin, interconnections are deleted to resolve the conflict.
Extensions of this technique to the control of crosstalk between routed interconnections and to the problem of obtaining 100 percent interconnect are also discussed.
The simplex method of linear programming using LU decomposition
Standard computer implementations of Dantzig's simplex method for linear programming are based upon forming the inverse of the basic matrix and updating the inverse after every step of the method. These implementations have bad round-off error properties. This paper gives the theoretical background for an implementation which is based upon the LU decomposition, computed with row interchanges, of the basic matrix. The implementation is slow, but has good round-off error behavior. The implementation appears as CACM Algorithm 350.
Rough and ready error estimates in Gaussian integration of analytic functions
Two expressions are derived for use in estimating the error in the numerical integration of analytic functions in terms of the maximum absolute value of the function in an appropriate region of regularity. These expressions are then specialized to the case of Gaussian integration rules, and the resulting error estimates are compared with those obtained by the use of tables of error coefficients.
Chebyshev interpolation and quadrature formulas of very high degree
All the zeros x2m,i, i = 1(1)2m, of the Chebyshev polynomials T2m(x), m = 0(1)n, are found recursively just by taking n2n-1 real square roots. For interpolation or integration of ƒ(x), given ƒ(x2m,i), only x2m,i is needed to calculate (a) the (2m - 1)-th degree Lagrange interpolation polynomial, and (b) the definite integral over [-1, 1], either with or without the weight function (1 - x2)-1/2, the former being exact for ƒ(x) of degree 2m+1 - 1.
An automatic grading scheme for simple programming exercises
A discussion is given of alterations that were made to a typical university operating system to record the results of programming exercises in three different languages, includeing assembly language. In this computer-controlled grading scheme provision is made for testing with programmer-supplied data and for final runs with system-supplied data. Exercises run under the scheme may be mixed with other programs, and no special recognition of exercises by the operators is necessary.
Dynamic space-sharing in computer systems
A formalization of relationships between space-sharing, program behavior, and processor efficiency in computer systems is presented. Concepts of value and cost of space allocation per task are defined and then value and cost are combined to develop a single parameter termed value per unit cost.
The intent is to illustrate a possible analytic approach to the investigation of the problems of space-sharing and to demonstrate the method on sample problems.
Clarification of Fortran standards—initial progress
In 1966, after four years of effort, FORTRAN became the first programming language standardized in the United States. Since that intital achievement, study and application of the standard specifications have revealed the need for maintenance of the standards. As the result of work intiated in 1967, as initial set of clarifying interpretations has been prepared. The nature of the maintenance, corrections to the standard specifications, and completed interpretations are reported.
