Search
Join ACM

Computing Applications

Advertisement

Research and Advances Jul 1 1984

Faster methods for random sampling

Several new methods are presented for selecting n records at random without replacement from a file containing N records. Each algorithm selects the records for the sample in a sequential manner—in the same order the records appear in the file. The algorithms are online in that the records for the sample are selected iteratively with no preprocessing. The algorithms require a constant amount of space and are short and easy to implement. The main result of this paper is the design and analysis of Algorithm D, which does the sampling in O(n) time, on the average; roughly n uniform random variates are generated, and approximately n exponentiation operations (of the form ab, for real numbers a and b) are performed during the sampling. This solves an open problem in the literature. CPU timings on a large mainframe computer indicate that Algorithm D is significantly faster than the sampling algorithms in use today.
Research and Advances Jul 1 1984

Efficient algorithms to globally balance a binary search tree

A binary search tree can be globally balanced by readjustment of pointers or with a sorting process in O(n) time, n being the total number of nodes. This paper presents three global balancing algorithms, one of which uses folding with the other two adopting parallel procedures. These algorithms show improvement in time efficiency over some sequential algorithms [1, 2, 7] when applied to large binary search trees. A comparison of various algorithms is presented.
and
Research and Advances Jun 1 1984

A large font virtual terminal interface: a software prosthesis for the visually impaired

A large font software interface running under UNIX1 is of great assistance to the severely visually impaired in the interactive use of computers. The interface, which functions as a virtual terminal as far as other processes are concerned, displays all characters (both user and system generated) at user-selectable degrees of magnification, yet is compatible with any standard CRT/keyboard terminal.
Opinion Jun 1 1984

From Washington: NSF takes the initiative

The National Science Foundation's Advisory Committee for Advanced Scientific Computing Resources was formed to provide leadership for large-scale scientific computing throughout the United States. Consisting of 15 members representing universities, industry, and national laboratories, the Committee held its first meeting in January 1984. A summary of the meeting issued by Chairman Neal F. Lane of Rice University makes the following points.
Research and Advances Jun 1 1984

Talking to UNIX in English: an overview of UC

UC is a natural language help facility which advises users in using the UNIX operating system. Users can query UC about how to do things, command names and formats, online definitions of UNIX or general operating systems terminology, and debugging problems in using commands. UC is comprised of the following components: a language analyzer and generator, a context and memory model, an experimental common-sense planner, highly extensible knowledge bases on both the UNIX domain and the English language, a goal analysis component, and a system for acquisition of new knowledge through instruction in English. The language interface of UC is based on a “phrasal analysis” approach which integrates semantic, grammatical and other types of information. In addition, it includes capabilities for ellipsis resolution and reference disambiguation.
, , and
Opinion Jun 1 1984

Programming pearls: graphic output

In previous columns we've studied the innards of programs. In this column we'll take a broader view of the programmer's task and consider the kind of output a program should produce. We'll focus on a single problem: once a system has produced detailed output, how can it summarize the trends in the mountain of data? The answer to that question depends heavily on both the data and the taste of the reader; paragraphs of text and tables of numbers often provide fine summaries. This column, however, will concetrate on graphical representations of data, which allow the powerful human vision system to understand data. A decade ago programmers could offer the excuse that they were limited to crude line printer graphics, but technology has changed that. Many large installations now have laser printers, and graphics printers for home computers sell for a few hundred dollars. This column is about ways that programmers can use the technology to deliver more useful (and more graphic) output.
Research and Advances Jun 1 1984

Anomalies in parallel branch-and-bound algorithms

We consider the effects of parallelizing branch-and-bound algorithms by expanding several live nodes simultaneously. It is shown that it is quite possible for a parallel branch-and-bound algorithm using n2 processors to take more time than one using n1 processors, even though n1 < n2. Furthermore, it is also possible to achieve speed-ups that are in excess of the ratio n2/n1. Experimental results with the 0/1-Knapsack and Traveling Salesman problems are also presented.
and
Research and Advances Jun 1 1984

Updating a database in an unsafe environment

Normally, when an application makes use of a database, considerable resources are invested in maintaining the integrity of that database. However, in situations where use of a database may be desirable even though the normal level of resources is unavailable, a simple technique using a partitioned data file protects the database if immediate transaction recording is not essential.
Research and Advances Jun 1 1984

Computer matching: should it be banned?

Since discovering the technique of computer matching several years ago, government managers have been invoking this computer tool in the attempt to root out waste and fraud in their programs. Is computer matching an indispensable tool for government administrators? Or a trampling on individual rights? In the following articles, two experts debate the pros and cons.
Research and Advances May 1 1984

A virtual memory system for picture processing

A virtual memory system designed specifically for picture processing, Raster Handler 2 provides programs with efficient access to pixels. It features square partition of images, imbalanced allocation of frames, and nondemand page replacement. RH2 is implemented in software and incorporates a prepaging algorithm designed specifically for picture processing.
Research and Advances May 1 1984

An algorithm for optimized Boolean evaluation in information management systems

In cases where simple data validation techniques are inadequate and optimization policies relatively complex (e.g., in health and medical systems), a Boolean optimization algorithm can be used to report errors accurately and unambiguously. The algorithm is presented in the context of a data-validating software module that uses an LR(1)-parser. The algorithm's precision makes it of potential use for the retrieval of records that nearly satisfy a query.
Research and Advances May 1 1984

Accommodating uncertainty in software design

Recognition that most software is domain dependent (DD) is extremely important because the most commonly used software life-cycle models are not adequate for DD software. The nature of DD software, and the need to manage its life cycle effectively, calls for a new approach to software design and the implementation of software development environments.
Research and Advances May 1 1984

Evolution and organizational information systems: an assessment of Nolan's stage model

Richard Nolan's stage model is the best known and most widely cited model of computing evolution in organizations. The model's development over a decade demonstrates its own evolution from a simple theory, based on the factoring of change states indicated by changes in computing budgets, to an elaborate account of the characteristics of six stages of computing growth. An analysis of the model's logical and empirical structure reveals a number of problems in its formulation that help to account for the fact that its principal tenets have not been independently validated. The model is shown to be an “evolutionistic” theory within the theories of evolution in the social sciences, focusing on assumed directions of growth and an implied end state toward which growth proceeds, and suffering from problems inherent in such theories. Further research based on an “evolutionary” view of computing growth is suggested as a means of improving theories of computing in organizations.
and
Research and Advances May 1 1984

Design of the S system for data analysis

S is a language and system for interactive data analysis and graphics. It emphasizes interactive analysis and graphics, ease of use, flexibility, and extensibility. While sharing many characteristics with other statistical systems, S differs significantly in its design goals, its implementation, and the way it is used. This paper presents some of the design concepts and implementation techniques in S and relates these general ideas in computing to the specific design goals for S and to other statistical systems.
and
Research and Advances May 1 1984

A critque of the stage hypothesis: theory and empirical evidence

The stage hypothesis on the assimilation of computing technology provides one of the most popular models for describing and managing the growth of administrative information systems. Despite little formal evidence of its reliability or robustness, it has achieved a high level of acceptance among practitioners. We describe and summarize the findings of seven empirical studies conducted during the past six years that tested various hypotheses derived from this model. The accumulation of evidence from these studies casts considerable doubt on the validity of the stage hypothesis as an explanatory structure for the growth of computing in organizations. 3~
, , , and

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