September 1983 - Vol. 26 No. 9
Features
From Washington: Secrecy versus scientific communication
There are many issues that affect the health of science but none more pervasive than the problem of “secrecy vs. scientific communication.” Unfortunately much of the debate on this issue, which is concern to all scientists, is being held behind closed doors among a few “key people.” The status of this debate was discussed in the August issue of Communications. More recent developments are reviewed here.
Programming pearls: Aha algorithms
The study of algorithms has much to offer the practicing programmer. After just a course or two on the subject, students take away algorithms for solving many important tasks and design techniques for attacking new problems. Advanced algorithmic tools can have a substantial impact on software systems. Next month, for instance, we'll study a system in which algorithm design helped reduce development time by 170 staff-years.
As important as such tools are, algorithms can have an impact on a more common level of programming. In his book aha! Insight (from which I shamelessly stole my title), Martin Gardner describes the type of contribution I have in mind: “a problem that seems difficult may have a simple, unexpected solution.” Unlike the advanced methods of the field, the aha! insights of algorithms don't come only after extensive study; they're available to any programmer willing to think seriously before, during, and after coding. But enough generalities, on to the problems!
Introduction to the fifth generation
In October 1981, Japan's Ministry of International Trade and Industry (MITI) sponsored a conference to announce a new national project. Alongside national projects in supercomputing and robotics, there would be an effort to develop a new generation (the fifth, by their reckoning) of computers.
The Japanese approach: a better way to manage programmers?
With a turnover rate among computer programmers of 25%-50% per year, it's time somebody came up with a better way to manage computer professionals. One approach that holds promise is to create a Japanese-style Theory Z atmosphere in the firm, stressing lifetime employment, non-specialized career paths, collective decision-making, and other holistic matters.
The fifth generation project — a trip report
As part of Japan's effort to become a leader in the computer industry, the Institute for New Generation Computer Technology has launched a revolutionary ten-year plan for the development of large computer systems which will be applicable to knowledge information processing systems. These Fifth Generation computers will be built around the concepts of logic programming. In order to refute the accusation that Japan exploits knowledge from abroad without contributing any of its own, this project will stimulate original research and will make its results available to the international research community.
Cooperation is key: an interview with B. R. Inman
The most innovative and audacious among the U.S. responses to Japan's Fifth Generation Project is that of the Microelectronics and Computer Technology Corp. MCC is a consortium of thirteen companies formed to conduct long range research and development in advanced computers. The member companies are investing in MCC projects in return for a three-year lead in implementing the resulting technology.
The President of MCC, retired Admiral B. R. Inman, must chart this new course for U.S. industrial research: a course of cooperation among competitors whose goal is to achieve U.S. supercomputer dominance in the 1990s marketplace.
A simple database language for personal computers
A simple database language for personal computers has been implemented by selecting a subset of the ANS MUMPS language and enhancing it so as to meet the requirements of microcomputer end-users who are unfamiliar with computers. This database language is named Micro MUMPS. Its database is based on a modified prefix B-tree having parameters for adjusting its data organization according to the requirements of space and time efficiency. Experience with Micro MUMPS has demonstrated a remarkable reduction in programming time.
A practical tool kit for making portable compilers
The Amsterdam Compiler Kit is an integrated collection of programs designed to simplify the task of producing portable (cross) compilers and interpreters. For each language to be compiled, a program (called a front end) must be written to translate the source program into a common intermediate code. This intermediate code can be optimized and then either directly interpreted or translated to the assembly language of the desired target machine. The paper describes the various pieces of the tool kit in some detail, as well as discussing the overall strategy.
An empirical study of insertion and deletion in binary search trees
This paper describes an experiment on the effect of insertions and deletions on the path length of unbalanced binary search trees. Repeatedly inserting and deleting nodes in a random binary tree yields a tree that is no longer random. The expected internal path length differs when different deletion algorithms are used. Previous empirical studies indicated that expected internal path length tends to decrease after repeated insertions and asymmetric deletions. This study shows that performing a larger number of insertions and asymmetric deletions actually increases the expected internal path length, and that for sufficiently large trees, the expected internal path length becomes worse than that of a random tree. With a symmetric deletion algorithm, however, the experiments indicate that performing a large number of insertions and deletions decreases the expected internal path length, and that the expected internal path length remains better than that of a random tree.
Optimal paths in graphs with stochastic or multidimensional weights
This paper explores computationally tractable formulations of stochastic and multidimensional optimal path problems, each as an extension of the shortest path problem. A single formulation encompassing both problems is considered, in which a utility function defines preference among candidate paths. The result is the ability to state explicit conditions for exact solutions using standard methods, and the applicability of well-understood approximation techniques.
A diagnosis of beginning programmers’ misconceptions of BASIC programming statements
In the process of learning a computer language, beginning programmers may develop mental models for the language. A mental model refers to the user's conception of the “invisible” information processing that occurs inside the computer between input and output. In this study, 30 undergraduate students learned BASIC through a self-paced, mastery manual and simultaneously had hands-on access to an Apple II computer. After instruction, the students were tested on their mental models for the execution of each of nine BASIC statements. The results show that beginning programmers—although able to perform adequately on mastery tests in program generation—possessed a wide range of misconceptions concerning the statements they had learned. This paper catalogs beginning programmers' conceptions of “what goes on inside the computer” for each of nine BASIC statements.
A quadtree medial axis transform
As printed
Quadtree skeletons are exact representations of the image and
are used because they are observed to yield space efficiently and a
decreased sensitivity to shifts in contrast with the quadtree. The
QMAT can be used as the underlying representation when solving most
problems that can be solved by using a quadtree. An algorithm is
presented for the computation of the QMAT of a given quadtree by
only examining each BLACK node's adjacent and abutting
neighbors.
Corrected Abstract (published as corrigendum in CACM 27, 2
(February 1984) p. 151)
The skeletal and medial axis transform concepts used in
traditional image processing representations are adapted to the
quadtree representation. The result is the definition of of a new
data structure termed the Quadtree Medial Axis Transform (QMAT). A
QMAT results in a partition of the image into a set of nondisjoint
squares having sides whose lengths are sums of powers of 2 rather
than, as is the case with quadtrees, a set of disjoint squares
having sides of lengths which are powers of 2. The motivation is
not to study skeletons for the usual purpose of obtainings
approximations of the image. Instead, quadtree skeletons are exact
representations of the image and are used because they are observed
to yield space efficiency and a decreased sensitvity to shifts in
contrast with the quadtree. The QMAT can be used as the underlying
representation when solving most problems that can be solved by
using a quadtree. An algorithm is presented for the computation of
the QMAT of a given quadtree by only examining each BLACK node's
adjacent and abutting neighbors. Analysis of the algorithm reveals
an average execution time proportional to the complexity of the
image, i.e., the number of BLACK blocks.
