GRAP—a language for typesetting graphs
The authors describe a system that makes it easy and convenient to describe graphs and to include them as an integral part of the document formatting process.
Jon L. Bentley
Advertisement
Author Archives
Amortized analyses of self-organizing sequential search heuristics
The performance of sequential search can be enhanced by the use of heuristics that move elements closer to the front of the list as they are found. Previous analyses have characterized the performance of such heuristics probabilistically. In this article, we use amortization to analyze the heuristics in a worst-case sense; the relative merit of the heuristics in this analysis is different in the probabilistic analyses. Experiments show that the behavior of the heuristics on real data is more closely described by the amortized analyses than by the probabilistic analyses.
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.
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