December 1974 - Vol. 17 No. 12
Features
Computer programming as an art
When Communications of the ACM began publication in 1959, the members of ACM's Editorial Board made the following remark as they described the purposes of ACM's periodicals [2]: “If computer programming is to become an important part of computer research and development, a transition of programming from an art to a disciplined science must be effected.” Such a goal has been a continually recurring theme during the ensuing years; for example, we read in 1970 of the “first steps toward transforming the art of programming into a science” [26]. Meanwhile we have actually succeeded in making our discipline a science, and in a remarkably simple way: merely by deciding to call it “computer science.”
Arguments for a moratorium on the construction of a community information utility
In this article the author urges a prudent and decentralized approach to the question of the design and desirability of computerized community information utilities. Before accepting the inevitability and desirability of this or any technology, we should: (1) be sure of the feasibility (internally and externally) of what is proposed; (2) project and perhaps wait for changes in complementary techniques; (3) evaluate current and projected supplementary techniques; (4) establish the existence of demand for what is proposed; (5) take steps to involve a representative group of ultimate users in systems design, and (6) carefully think through possible side effects on man and his world view.
Current proposals for community information utilities are examined in this framework, and the conclusion is drawn that society is not yet in a position to justify either the construction of an information utility in a prototype community or the acceptance of a policy in favor of its widespread implementation.
An analytic model of the HASP execution task monitor
The HASP Execution Task Monitor periodically rearranges the OS/360 dispatching chain to give tasks preemptive execution priority in inverse order to that of their cpu utilization history. The effect is to keep the I/O bound tasks active and to prevent cpu bound tasks from locking out other tasks. This paper develops a simple model of the Execution Task Monitor and employs it to study the effectiveness of the monitor in improving system performance. A modified strategy for monitor control is investigated for the case of task execution in a memory heirarchy of varying speeds.
A comparison of list schedules for parallel processing systems
The problem of scheduling two or more processors to minimize the execution time of a program which consists of a set of partially ordered tasks is studied. Cases where task execution times are deterministic and others in which execution times are random variables are analyzed. It is shown that different algorithms suggested in the literature vary significantly in execution time and that the B-schedule of Coffman and Graham is near-optimal. A dynamic programming solution for the case in which execution times are random variables is presented.
Computer generation of gamma random variates with non-integral shape parameters
When the shape parameter, &agr;, is integral, generating gamma random variables with a digital computer is straightforward. There is no simple method for generating gamma random variates with non-integral shape parameters. A common procedure is to approximately generate such random variables by use of the so-called probability switch method. Another procedure, which is exact, is due to Jöhnk. This paper presents a rejection method for exactly generating gamma random variables when &agr; is greater than 1. The efficiency of the rejection method is shown to be better than the efficiency of Jöhnk's method. The paper concludes that when &agr; is non-integral the following mix of procedures yields the best combination of accuracy and efficiency: (1) when &agr; is less than 1, use Jöhnk's method; (2) when 1 is less than &agr; and &agr; is less than 5, use the rejection method; (3) when &agr; is greater than 5, use the probability switch method.
A graph formulation of a school scheduling algorithm
The problem classically titled “The Examination Schedule Problem” takes various forms in the literature. Most of these formulations can be presented in the terminology of classical Network Theory. One such formulation is: Given a nondirected network, partition its nodes into a minimal number of subsets such that no two members of the same subset are connected by an arc.
An obvious lower limit to this number is the size of the largest strongly connected subgraph. Kirchgassner proved that an upper limit is this size plus one.
One logical extension of the previous work is the introduction of variable length examinations where W(I) is the number of periods for exam I. The object of this paper is to generalize the definition of largest strongly connected subgraph to include the weighting of nodes, to present an approximate algorithm which usually finds the largest strongly connected subgraph, and to discuss the application of this algorithm to the solution of school scheduling and exam scheduling problems.
An exponential method for the solution of systems of ordinary differential equations
An explicit, coupled, single-step method for the numerical solution of initial value problems for systems of ordinary differential equations is presented. The method was designed to be general purpose in nature but to be especially efficient when dealing with stiff systems of differential equations. It is, in general, second order except for the case of a linear system with constant coefficients and linear forcing terms; in that case, the method is third order. It has been implemented and put to routine usage in biological applications—where stiffness frequently appears—with favorable results. When compared to a standard fourth order Runge-Kutta implementation, computation time required by this method has ranged from comparable for certain nonstiff problems to better than two orders of magnitude faster for some highly stiff systems.
Algorithm 488: A Gaussian pseudo-random number generator
The algorithm calculates the exact cumulative distribution of the two-sided Kolmogorov-Smirnov statistic for samples with few observations. The general problem for which the formula is needed is to assess the probability that a particular sample comes from a proposed distribution. The problem arises specifically in data sampling and in discrete system simulation. Typically, some finite number of observations are available, and some underlying distribution is being considered as characterizing the source of the observations.
A heuristic approach to inductive inference in fact retrieval systems
Heuristic procedures are presented which have been developed to perform inferences by generalizing from available information. The procedures make use of a similarity structure which is imposed on the data base using nonnumerical clustering algorithms. They are implemented in a model fact retrieval system which uses a formal query language and a property-list data structure. A program of experiments is described wherein the procedures are used with test data bases which are altered by deleting part of the data and by purposely introducing false data. It is found that the system can infer the correct response under a variety of conditions involving incomplete and inconsistent data.
