Software Engineering and Programming Languages Archives - Page 249 of 283

Research and Advances Feb 1 1984

The operational versus the conventional approach to software development

The conventional approach to software development is being challenged by new ideas, many of which can be organized into an alternative decision structure called the “operational” approach. The operational approach is explained and compared to the conventional one.

Pamela Zave

Research and Advances Jan 1 1984

Some negative results concerning prime number generators

Programs attributed to Wirth and Misra for generating the prime numbers up to a specified limit are investigated. It is shown that Wirth's program is incorrect according to three increasingly weak criteria, and a composite number is exhibited that the program accepts as prime. This is the smallest known counterexample, and could not have been found by the usual method of program testing—the program would run for trillions of years on the fastest computer before reaching it! Closely related counterexamples are given to a conjecture of Misra concerning his program. An appendix gives a particularly simple algorithmic proof of the Chinese remainder theorem.

Paul Pritchard

Opinion Jan 1 1984

President’s letter

David Brandin

Research and Advances Jan 1 1984

Assessing software maintainability

How easy is it to maintain a program? To a large extent, that depends on how difficult the program is to understand. A technique to measure program difficulty yields encouraging results.

Gerald M. Berns

Opinion Jan 1 1984

ACM Forum: Letters

Robert L. Ashenhurst

Research and Advances Jan 1 1984

Self-assessment procedure XII: a self-assessment procedure dealing with computer architecture

Robert I. Winner and Edward M. Carter

Research and Advances Jan 1 1984

Software errors and complexity: an empirical investigation0

An analysis of the distributions and relationships derived from the change data collected during development of a medium-scale software project produces some surprising insights into the factors influencing software development. Among these are the tradeoffs between modifying an existing module as opposed to creating a new one, and the relationship between module size and error proneness.

Victor R. Basili and Barry T. Perricone

Research and Advances Jan 1 1984

Requirements analysis for Ada compilers

A Guide to the Selection and Specification of Ada Compilers was recently produced by the Portability Working Group of Ada-Europe. Most of the points addressed are applicable criteria for evaluation of any language compiler.

Peter J. L. Wallis and Brian A. Wichmann

Research and Advances Dec 1 1983

Reducing the retrieval time of hashing method by using predictors

Many methods for resolving collisions in hashing techniques have been proposed. They are classified into two main categories: open addressing and chaining. In this paper, other methods are presented that are intermediate between the two categories. The basic idea of our methods is the use of one or more predictors reserved per cell instead of a link field as in the chaining method. The predictors are used to maintain loose synonym chains. After describing the methods, the efficiencies are estimated theoretically and verified experimentally. In comparison with the chaining method, we prove that our methods significantly reduce the average number of probes necessary to retrieve a key without expending extra space.

Seiichi Nishihara and Katsuo Ikeda

Research and Advances Dec 1 1983

A user-friendly software environment for the novice programmer

SOLO, a nonnumerical programming language, was developed at The Open University in the U.K. to support a course on Cognitive Psychology. It was designed to acquaint students as painlessly as possible with the computing fundamentals necessary both to grasp AI principles as applied in Cognitive Psychology and to actually initiate fairly sophisticated exercises on their own. The language has been used successfully by more than 2500 social science students.

Marc Eisenstadt

Research and Advances Dec 1 1983

Balancing binary trees by internal path reduction

We present an algorithm for balancing binary search trees. In this algorithm single or double rotations are performed when they decrease the internal path of the total tree. It is shown that the worst internal path on such trees is never more than 5 percent worse than optimal and that its height is never more than 44 percent taller than optimal. This compares favorably with the AVL trees whose internal path may be 28 percent worse than optimal and the same 44 percent worst height, and with the weight-balanced trees which may be 15 and 100 percent worse than optimal, respectively. On the other hand, the number of rotations during a single insertion/deletion can be O(n), although the amortized worst-case number of rotations is O(log n) per update.

Gaston H. Gonnet

Research and Advances Dec 1 1983

Transporting a portable operating system: UNIX to an IBM minicomputer

The “portable” UNIX operating system was transported to an IBM Series/1 minicomputer. The process of transporting is described with emphasis on (1) adapting to the target machine architecture; (2) the selection of the approach taken to transporting; (3) a description of the problems encountered; (4) the degree of portability of the UNIX system; and (5) a summary of the portability lessons learned.

Paul J. Jalics and Thomas S. Heines