June 1980 - Vol. 23 No. 6

June 1980 issue cover image


Research and Advances

Comments on program specification and testing

The data processing discipline is in a deplorable state, says Roger House. The author reviews an earlier study, in which programmers were largely unsuccessful in finding known errors in a test program. House shows that the fault lies not with the subjects but with the generally poor procedures underlying the writing of much contemporary software, including the test program in question. He analyzes the example, offers several specific critiques, and enumerates good software-writing practices.
Research and Advances

Computer assisted instruction: current trends and critical issues

The use of computers to assist in the learning situation in a simulation, game, tutorial, or drill and practice mode is reviewed on an international basis with centers of activity identified in the United States, Canada, the United Kingdom, and Japan. The use of the computer as an adjunct to support learning is compared to its use in a substitution mode. Evaluative studies of CAI are reviewed and costs are examined. The critical issues of CAI are enumerated and analyzed as they pertain to computer hardware, CAI languages, and courseware development and use. The future of CAI is briefly sketched from the viewpoints of individuals prominent in the field. Finally, conclusions are drawn and recommendations are offered to help ensure the most educationally cost-effective use of CAI in learning situations.
Research and Advances

An improved illumination model for shaded display

To accurately render a two-dimensional image of a three-dimensional scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this information is stored in a tree of “rays” extending from the viewer to the first surface encountered and from there to other surfaces and to the light sources. A visible surface algorithm creates this tree for each pixel of the display and passes it to the shader. The shader then traverses the tree to determine the intensity of the light received by the viewer. Consideration of all of these factors allows the shader to accurately simulate true reflection, shadows, and refraction, as well as the effects simulated by conventional shaders. Anti-aliasing is included as an integral part of the visibility calculations. Surfaces displayed include curved as well as polygonal surfaces.
Research and Advances

A more general algorithm for computing closed semiring costs between vertices of a directed graph

This note describes a generalization of an algorithm given by Aho, Hopcroft, and Ullman [1], originally derived from the work of Kleene [2] and McNaughton and Yamada [3]. The algorithm is used to compute the total cost of all paths between each pair of vertices in a directed graph when the cost of each edge is known. The cost of a path is defined as the product of the costs of the edges forming it, and the total cost of a set of paths is the sum of their individual costs. If there are n vertices labeled 1 through n and E[i, j] is the cost of the edge from vertex i to vertex j (or is zero when there is no such edge), then the total cost T[i, j] of all paths from i to j is the solution of the equation T[i, j] = &dgr;[i, j] + ∑nk-1 E[i, k]·T[k, j], (1) where &dgr;[i, i] = 1 (the cost of the path of no edges from i to i) and &dgr;[i, j] = 0 if i ≠ j. To assure that T [i, j] is always well-defined, costs are required to be elements from an algebraic structure called a closed semiring.

Recent Issues

  1. July 2024 CACM cover
    July 2024 Vol. 67 No. 7
  2. June 2024 Vol. 67 No. 6
  3. May 2024 CACM cover
    May 2024 Vol. 67 No. 5
  4. April 2024 CACM cover with text
    April 2024 Vol. 67 No. 4