Sign In

Communications of the ACM

Table of Contents


President's letter

ACM forum

Computer science: the emergence of a discipline

The continued rapid development of computer science will require an expansion of the science base and an influx of talented new researchers. Computers have already altered the way we think and live; now they will begin to elevate …

Algorithm design

The quest for efficiency in computational methods yields not only fast algorithms, but also insights that lead to elegant, simple, and general problem-solving methods.

Automatic correction to misspelled names: a fourth-generation language approach

Using an information theoretic likeness measure defined as an inner product on a data space created from a table of valid names, this 4GL procedure searches the database space for the nearest correctly spelled name.

Functionality and usability

Instead of limiting functionality, usability complements functionality. It affects how and with what effectiveness a system is used, and even whether or not it is used at all.

Pairing heaps: experiments and analysis

The pairing heap has recently been introduced as a new data structure for priority queues. Pairing heaps are extremely simple to implement and seem to be very efficient in practice, but they are difficult to analyze theoretically …

The effect of data structures on the logical complexity of programs

The logical complexity of a program is a measure of the effort required to understand it. We hypothesize that the logical complexity of a program increases with the increase in the opaqueness of the relationship between the physical …

Technical correspondence

An interview with the 1986 A. M. Turing Award recipients—John E. Hopcroft and Robert E. Tarjan

In the following interview, which took place at the 1986 Fall Joint Computer Conference in Dallas, Texas, John Hopcroft and Robert Tarjan discuss their collaboration and its influence on their separate research today. They also …