Search
Join ACM

Computing Applications

Advertisement

Research and Advances

An on-line algorithm for fitting straight lines between data ranges

Applications often require fitting straight lines to data that is input incrementally. The case where a data range [&agr;k, &ohgr;k] is received at each tk, t1 < t2 < … tn, is considered. An algorithm is presented that finds all the straight lines u = mt + b that pierce each data range, i.e., all pairs (m, b) such that &agr;k ≤ mtk + b ≤ &ohgr;k for k = 1, … , n. It may be that no single line fits all the ranges, and different alternatives for handling this possibility are considered. The algorithm is on-line, producing the correct partial result after processing the first k ranges for all k < n. For each k, the set of (m, b) pairs constitutes a convex polygon in the m-b parameter space, which can be constructed as the intersection of 2k half-planes. It is shown that the O(n logn) half-plane intersection algorithm of Shamos and Hoey can be improved in this special case to O(n).
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

Polynomial manipulation with APL

A simple but effective method for the manipulation of polynomials of several variables in APL is presented. The method is especially advantageous in situations where more sophisticated symbolic computing systems such as SAC-1 and MACSYMA are not available. The method is shown to successfully solve a problem not readily resolved by other means.
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

Representing super-sparse matrices with perturbed values

This paper describes a form of purposeful data perturbation in a linear programming model which pertains to uncertainties in the magnitudes of the matrix coefficients. A problem in value pool construction is described first, then a resolution based on a new concept, “covering lattices.” Computer representations of real values, limited by finite precision, is an example of a covering lattice. After presenting the strategy and tactical variations, the effects of resident distortion are analyzed. Several theorems are presented that measure bias under a variety of assumptions. An appendix is included that contains mathematical proofs.
and
Research and Advances

Response to the Federal Trade Commission’s proposed ruling on standards and certification

In December 1978, the Federal Trade Commission issued a notice of intention of rulemaking in regard to the matter of Standards and Certification. In cooperation with the American National Standards Institute, of which ACM is a member, the ACM Standards Committee prepared a response to that notice and submitted it to the Commission in April 1979. The response gives a summary of the ACM Standards Committee position on a standards regulation and affords insights into the process by which procedures evolve in this area. For this reason, the response is reproduced here as a report.
Research and Advances

Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography

A new paradigm, Random Sample Consensus (RANSAC), for fitting a model to experimental data is introduced. RANSAC is capable of interpreting/smoothing data containing a significant percentage of gross errors, and is thus ideally suited for applications in automated image analysis where interpretation is based on the data provided by error-prone feature detectors. A major portion of this paper describes the application of RANSAC to the Location Determination Problem (LDP): Given an image depicting a set of landmarks with known locations, determine that point in space from which the image was obtained. In response to a RANSAC requirement, new results are derived on the minimum number of landmarks needed to obtain a solution, and algorithms are presented for computing these minimum-landmark solutions in closed form. These results provide the basis for an automatic system that can solve the LDP under difficult viewing
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.
Opinion

ACM president’s letter: eating our seed corn

On July 12 and 13, 1980, the biennial meeting of Computer Science Department chairmen was held at Snowbird, Utah. This meeting, which is organized by the Computer Science Board (CSB), is a forum for the heads of the 83 departments in the United States and Canada that grant Ph.D.s in Computer Science. The meeting was attended by 56 department heads or their representatives, and by six observers from industry and government. This report was developed during the meeting as a result of intensive discussions about the crisis in Computer Science. This report was endorsed by the entire assembly.
Research and Advances

Quo Vadimus: computer science in a decade

A panel discussion was held during the third biennial meeting of chairmen of Ph.D.-granting computer science departments in June, 1978 at Snowbird, Utah, a meeting sponsored by the Computer Science Board. Invitees from industry and government were also present. A report was prepared from tapes made of the discussion (Department of Computer Science, Carnegie-Mellon University: Report #CMU-CS-80-127, June 1980). It contained all the prepared statements of the panelists, lightly edited, and the panelists' discussion in its entirety. A selection of the audience discussion was also included, rather heavily edited. The following presentation is derived from that report.

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