Advertisement

Research and Advances

Can computers cope with human races?

In trying to apply a computer to a task that humans do, we often discover that it doesn't work. One common problem is that humans are able to deal with fuzzy concepts, but computers are not—they need precise representations and it is hard to represent a fuzzy concept in a precise way. However, if we look closer at such tasks, we often discover that the weakness actually lies not in the computer but in ourselves—that we didn't understand what we were doing in the first place. When faced with a problem of this sort, some people refuse to recognize the conceptual failure. Instead of seeking a better representation for the task, they thrash away at making the fuzzy scheme work, insisting that there is nothing wrong with the conceptual base. I will illustrate one such problem with a true story. The central theme is the fuzzy concept of racial and ethnic classification, as used by the U.S. government and a horde of other bureaucracies. These organizations have been carrying out elaborate statistical computations and making major policy decisions based on this concept for many years with problematical results. I begin with my first encounter with this scheme, some 25 years ago.
Research and Advances

Spreadsheet analysis and design

Although spreadsheet programs and microcomputers have revolutionized information processing in organizations, a significant number of serious errors have been reported through the misuse of this technology. This article discusses several different contexts for the development of spreadsheet models and presents structured design techniques for these models.
Research and Advances

A field study of the software design process for large systems

The problems of designing large software systems were studied through interviewing personnel from 17 large projects. A layered behavioral model is used to analyze how three of these problems—the thin spread of application domain knowledge, fluctuating and conflicting requirements, and communication bottlenecks and breakdowns—affected software productivity and quality through their impact on cognitive, social, and organizational processes.
Research and Advances

Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation

The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap—a sequence of m decrease_key and n delete_min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case—O(1) time for decrease_key and O(log n) for delete_min. Relaxed heaps give a processor-efficient parallel implementation of Dijkstra's shortest path algorithm, and hence other algorithms in network optimization. A relaxed heap is a type of binomial queue that allows heap order to be violated.
Research and Advances

Ecological studies of professional programmers

For over two decades, software psychology researchers have been developing insights to software productivity and quality by investigating builders and users of software. This research has been diverse in both its approach and its impacts. It has introduced systematic behavioral measurement into the software development process and into research on new software techniques and technologies, and has also opened up new social and cognitive interpretations of software processes [5, 12]. We now see evidence of a new thrust in software psychology coming to the fore, one in which usability researchers are direct participants in the definition and creation of new software artifacts. We call this paradigm Ecological Design, to emphasize (1) that realistic software situations are being confronted on their own terms, and (2) that the work is directed toward design results, not merely toward evaluation and description in the service of design goals. The reorientation towards studying teamwork was prompted in 1971 by Weinberg and followed by a few researchers at that time, but the movement has accelerated with the recent and intense interest in computer supported collaborative work [15]. This was apparent in the papers presented at the two workshops on Empirical Studies of Programmers [10, 13]. An accompanying shift has also occurred in the software engineering community. The traditional waterfall model of software development with the precise specification of a provable topdown design is giving way to newer exploratory styles of program development that emphasize rapid prototyping and iterative refinement. The shift from product to process also puts greater emphasis on team organization, group processes, management policies, reusability, development tools, design methods, debugging strategies, and maintenance [6]. The three papers in this special section exemplify this new paradigm. Rosson, Maass, and Kellogg and Curtis, Krasner, and Iscoe describe highly qualitative studies of professional designers that produced specific technical proposals for improving software tools and the coordination of project management, an assessment of major bottlenecks, and a new framework for thinking about software design as a learning and communication process. Soloway, Pinto, Letovsky, Littman, and Lampert describe the design and exploration of software documentation that grew out of similarly qualitative studies of program maintenance. We caution that this research paradigm is still in its infancy: setting design requirements and developing prototypes are not traditional activities of psychological researchers. These roles are still emerging, still being reconciled with the earlier paradigms. The particular projects highlighted here are only the beginning; the field continues to evolve, as more researchers are attracted, as more topics are explored, as more methods are developed. Thus, despite the shortcomings of any particular project, the trajectory of this paradigm seems clear to us: it is the development of ideas that directly impact productivity and quality in software. Indeed, part of our intention in presenting this special section is to encourage more and more rapid development of the new paradigm.
Research and Advances

The designer as user: building requirements for design tools from design practice

Software tools that support the design and development of interactive computing systems are an exciting possibility. The potential pay-off is great: user interface management systems, for example, promise not only to speed the process of specifying, implementing and maintaining user interface code, but also to guide the content of the user interfaces they support. As for any tool intended for human use, however, the success of software design tools will hinge on a thorough understanding of the problems they seek to address—design as it is practiced in the real world.
Research and Advances

The number of buffers required for sequential processing of a disk file

The number of buffers required for sequential processing of disk files is investigated with the assumption that there is a single user served by two processors: one reads blocks from the disk into buffers in main memory, while the other processor processes the buffers. If processing is faster than reading, then two buffers suffice. However, if processing is slower, using only two buffers does not guarantee minimum completion time. The minimal required number of buffers is calculated in this article.
Research and Advances

Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem

A new priority queue implementation for the future event set problem is described in this article. The new implementation is shown experimentally to be O(1) in queue size for the priority increment distributions recently considered by Jones in his review article. It displays hold times three times shorter than splay trees for a queue size of 10,000 events. The new implementation, called a calendar queue, is a very simple structure of the multiple list variety using a novel solution to the overflow problem.
Research and Advances

Computers and elections

Along the twists and turns of this year's presidential campaign trails, computers act as strategic tools that exert a decisive impact on capturing voters' attention. But a National Bureau of Standards study claims that system implementations are dangerously inadequate at the finish line, where carefully gleaned votes are less carefully counted.

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