December 1983 - Vol. 26 No. 12
Features
Programming pearls: Writing correct programs
In the late 1960s people were talking about the promise of programs that verify the correctness of other programs. Unfortunately, it is now the middle of the 1980s, and, with precious few exceptions, there is still little more than talk about automated verification systems. Despite unrealized expectations, however, the research on program verification has given us something far more valuable than a black box that gobbles programs and flashes “good” or “bad”—we now have a fundamental understanding of computer programming.
The purpose of this column is to show how that fundamental understanding can help programmers write correct programs. But before we get to the subject itself, we must keep it in perspective. Coding skill is just one small part of writing correct programs. The majority of the task is the subject of the three previous columns: problem definition, algorithm design, and data structure selection. If you perform those tasks well, then writing correct code is usually easy.
Meeting the crisis in computer science
Participants in the 1982 Snowbird Conference reassessed the problems in computer science education and recommended steps for improvement.
A survey of attitudes toward computers
What do people really think about computers and their impact? In 1970, a study of people's attitudes in North America showed computers to be regarded as either “beneficial tools of mankind” or as “awesome thinking machines.” A recent survey taken in Australia and reported in this article, though, suggests there may have been a change in attitudes over the past decade. The Australians expressed much concern over the computer's possible disemploying and dehumanizing effects—as well as disquiet over the control computers could exercise over their lives. If these attitudes are typical beyond the shores of Australia, they could create a barrier to the widespread acceptance and application of computers around the world.
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.
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.
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.
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.
