Search
Join ACM

Software Engineering and Programming Languages

Advertisement

Research and Advances

Comparison of synonym handling and bucket organization methods

A theoretical description of the access times required in open addressing and external chaining is given. Values are calculated for different record and bucket sizes and load factors, and the corresponding values for the two methods are compared. Practical guidelines for determining bucket sizes and load factors are presented. It is proved that open addressing is almost always superior to external chaining and the optimal bucket size is between 1 and 4.
Research and Advances

System design for usability

The factors underlying system design for usability are examined and the role and responsibilities of a usability committee described. Under the control of a usability committee, a balance between high levels of system function and usability was reached for the IBM System/38. The System/38 command language is presented to illustrate this balance.
Research and Advances

Long term file migration: development and evaluation of algorithms

The steady increase in the power and complexity of modern computer systems has encouraged the implementation of automatic file migration systems which move files dynamically between mass storage devices and disk in response to user reference patterns. Using information describing 13 months of user disk data set file references, we develop and evaluate (replacement) algorithms for the selection of files to be moved from disk to mass storage. Our approach is general and demonstrates a general methodology for this type of problem. We find that algorithms based on both the file size and the time since the file was last used work well. The best realizable algorithms tested condition on the empirical distribution of the times between file references. Acceptable results are also obtained by selecting for replacement that file whose size times time to most recent reference is maximal. Comparisons are made with a number of standard algorithms developed for paging, such as Working Set, VMIN, and GOPT. Sufficient information (parameter values, fitted equations) is provided so that our algorithms may be easily implemented on other systems.
Research and Advances

Psychology of calculator languages: a framework for describing differences in users' knowledge

This paper presents a framework for describing users' knowledge of how a simple four-function calculator operates. Differences among novices and experts in their conceptions of “what goes on inside the calculator” for various sequences of button presses are summarized. Individual differences include different views on when an expression is evaluated, different procedures for evaluating a chain of arithmetic, and different rules for evaluating unusual sequences of key presses.
and
Research and Advances

Mxec: parallel processing with an advanced macro facility

Mxec is a sophisticated computing environment (executive system) which extends and magnifies users' interactions with a computer. Principally, Mxec provides for parallel processing and also assumes many of the mundane, clerical tasks with which users of most systems find themselves burdened. Some of the characteristics of the Mxec system are given, and its motivation and implementation are discussed.
Research and Advances

On the security of multiple encryption

Double encryption has been suggested to strengthen the Federal Data Encryption Standard (DES). A recent proposal suggests that using two 56-bit keys but enciphering 3 times (encrypt with a first key, decrypt with a second key, then encrypt with the first key again) increases security over simple double encryption. This paper shows that although either technique significantly improves security over single encryption, the new technique does not significantly increase security over simple double encryption. Cryptanalysis of the 112-bit key requires about 256 operations and words of memory, using a chosen plaintext attack. While DES is used as an example, the technique is applicable to any similar cipher.
and
Research and Advances

Triform programs

The concept that three process functions—initialization, production, and completion—and a separate supervisory control function are sufficient to describe the execution of a program is the basis for Triform Program design. Triform programs are composed of modules arranged in a trifurcate tree structure with each branch devoted to the performance of one and only one of the process functions. The root of the program tree is a control module which supervises process-function execution. Such trifurcate tree structures are shown to be minimum complexity structures.
Research and Advances

The cube-connected cycles: a versatile network for parallel computation

An interconnection pattern of processing elements, the cube-connected cycles (CCC), is introduced which can be used as a general purpose parallel processor. Because its design complies with present technological constraints, the CCC can also be used in the layout of many specialized large scale integrated circuits (VLSI). By combining the principles of parallelism and pipelining, the CCC can emulate the cube-connected machine and the shuffle-exchange network with no significant degradation of performance but with a more compact structure. We describe in detail how to program the CCC for efficiently solving a large class of problems that include Fast Fourier transform, sorting, permutations, and derived algorithms.
and
Research and Advances

Updating a master file—yet one more time

For several years I have been teaching a file updating algorithm which is essentially the same as that in Dwyer's admirable paper [1]. There is one unjustified objection to the algorithm that perceptive students and people with batch processing experience almost invariably raise and which is not addressed by Dwyer. The objection is based on a situation which arises in a batch processing environment with several users, where key-ordered sequential update is used.
Research and Advances

Experience with a space efficient way to store a dictionary

The paper, “Computer Programs for Detecting and Correcting Spelling Errors” by James L. Peterson [3], listed methods for checking and correcting spelling errors. One significant method, however, was not included: a probabilistic technique suggested by Carter, Floyd, Gill, Markovsky, and Wegman [1]. The present note discusses aspects of these practical space efficient algorithms for testing set membership—a simple abstraction of looking a word up in a dictionary. An implementation of one of these algorithms uses only 20 percent of the space used by the Stanford SPELL program described by Peterson.
Research and Advances

Another spelling correction program

We read James L. Peterson's article, “Computer Programs for Detecting and Correcting Spelling Errors” with great interest. We too have recently developed a spelling correction program as part of a tutorial on programming techniques and style. Our basic modesty inhibited us from publishing the details—there was, after all, little research involved in making the program. However, on reflection, there are several features in our design that we feel merit wider circulation.
and
Research and Advances

Parallel programs: proofs, principles, and practice

Several principles are identified from work on the verification of parallel programs. Concrete examples of the ways these principles can be applied, even when formal verification is not the goal, are then described. The purpose of this paper is to demonstrate ways in which the concepts of program verification yield insight into the programming process, programming languages, and program properties.

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