Search
Join ACM

Computing Applications

Advertisement

Research and Advances Sep 1 1982

Designing computer system messages

tive computer systems and studies of their users, we have become increasingly aware of the importance of system messages. Novice users are unimpressed with CPU speeds, disk storage capabilities, or elegant file structures. For them, the system appears only in the form of the messages on their screens or printers. So when novices encounter violent messages such as “FATAL ERROR, RUN ABORTED”, vague phases like “ILLEGAL CMD”, or obscure codes such as “OC7” or “IEH2191”, they are understandably shaken, confused, dismayed, and discouraged from continuing. The negative image that computer systems sometimes generate is, we believe, largely due to the difficulties users experience when they make mistakes or are unsure about what to do next.
Research and Advances Sep 1 1982

Algorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation

This paper discusses a family of algorithms for computing the volume, moments of inertia, and other integral properties of geometrically complex solids, e.g. typical mechanical parts. The algorithms produce approximate decompositions of solids into cuboid cells whose integral properties are easy to compute. The paper focuses on versions of the algorithms which operate on solids represented by Constructive Solid Geometry (CSG), i.e., as set-theoretical combinations of primitive solid “building blocks.” Two known algorithms are summarized and a new algorithm is presented. The efficiencies and accuracies of the three algorithms are analyzed theoretically and compared experimentally. The new algorithm uses recursive subdivision to convert CSG representations of complex solids into approximate cellular decompositions based on variably sized blocks. Experimental data show that the new algorithm is efficient and has predictable accuracy. It also has other potential applications, e.g., in producing approximate octree representations of complex solids and in robot navigation.
and
Opinion Sep 1 1982

Letters to the editor: A protection model and its implementation in a dataflow system

A protection model is presented for a general purpose computing system based on tags attached as seals and signatures to values exchanged among processes. A tag attached to a value as a seal does not prevent that value from being propagated to any place within the system; rather, it guarantees that the value and any information derived from it cannot leave the system unless a matching tag is presented. A tag attached to a value as a signature is used by a process to verify the origin of the received data. Solutions to problems from the areas of interprocess communication and proprietary services are given.
Research and Advances Sep 1 1982

Designing a Bloom filter for differential file access

The use of a differential file for a database update can yield integrity and performance benefits, but it can also present problems in providing current data to subsequent accessing transactions. A mechanism known as a Bloom filter can solve these problems by preventing most unnecessary searches of the differential file. Here, the design process for a Bloom filter for an on-line student database is described, and it is shown that a very effective filter can be constructed with a modest expenditure of system resources.
Research and Advances Sep 1 1982

Efficient parallel algorithms for some graph problems

We study parallel algorithms for a number of graph problems, using the Single Instruction Stream-Multiple Data Stream model. We assume that the processors have access to a common memory and that no memory or data alignment time penalties are incurred. We derive a general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph. In particular, an O(log2 n) time bound can be achieved using only K = n⌈n/log2 n⌉ processors. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.
, , and
Research and Advances Sep 1 1982

U.S. computer export control policies: value conflicts and policy choices

The formulation of a balanced and effective export control policy for computer products and know-how has been an important and difficult task for both the U.S. Government and the computing community. External pressures force national security concerns to conflict with the values and interests of private enterprise and academic freedom. This paper has two primary objectives: the first is to present the computing community with a reasonably equitable and detailed perspective on this important public policy problem; the second is to present and analyze a range of policy choices.
Research and Advances Sep 1 1982

A program testing assistant

This paper describes the design and implementation of a program testing assistant which aids a programmer in the definition, execution, and modification of test cases during incremental program development. The testing assistant helps in the interactive definition of test cases and executes them automatically when appropriate. It modifies test cases to preserve their usefulness when the program they test undergoes certain types of design changes. The testing assistant acts as a fully integrated part of the programming environment and cooperates with existing programming tools such as a display editor, compiler, interpreter, and debugger.
Research and Advances Sep 1 1982

File archival techniques using data compression

The performance of most small computer systems is determined, to a large extent, by the characteristics of their mass storage devices. Data compression can expand the storage capacity of such devices and also slightly increase their speed. Here, a summary of one method of data compression using Huffman variable length coding is presented, along with statistics of effectiveness for various file types and practical techniques for integrating such methods into a small computer system.
Research and Advances Jul 1 1982

Principles of package design

Subprogram packages are groups of related subroutines used to extend the available facilities in a programming system. The results of developing several such packages for various applications are presented, with a distinction made between external and internal design criteria— what properties packages should offer to their users and the guidelines designers should follow in order to provide them. An important issue, the design of reusable software, is thus addressed, and the concept of abstract data types proposed as a desirable solution.
Research and Advances Jul 1 1982

Authoring systems in computer based education

The idea of a programming system which generates other programs (referred to as automatic programming or metasoftware) has always been a popular one in computer science. Despite the interest, however, few such systems have actually been inplemented and used. An exception is the development and use of authoring systems in the domain of Computer Based Education (CBE). This article surveys the development and characteristics of authoring systems.
Research and Advances Jul 1 1982

Controlling the complexity of menu networks

A common approach to the design of user interfaces for computer systems is the menu selection technique. Each menu frame can be considered a node in an information/action network. The set of nodes and the permissible transitions between them (menu selections) form a directed graph which, in a system of substantial size, can be large and enormously complex. The solution to this problem of unmanageable complexity is the same for menu networks as for programs: the disciplined use of a set of well-defined one-in-one-out structures. This paper defines a set of such structures and offers some guidelines for their use.
Research and Advances Jul 1 1982

Estimating block accesses and number of records in file management

We consider the problems of estimating the number of secondary storage blocks and the number of distinct records accessed when a transaction consisting of possibly duplicate requested records is presented to a file management system. Our main results include (1) a new formula for block access estimation for the case where the requested records may have duplications and their ordering in immaterial and (2) a simple formula for estimating the number of distinct records in the transaction.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More