Sign In

Communications of the ACM

Table of Contents


President's Letter


ACM Forum: letters


Programming pearls: updates


An MCC update


Computer graphics comes of age: an interview with Andries Van Dam

Andries van Dam describes major advances in computer graphics over the past 25 years and discusses future directions.

The TWA reservation system

Where can you find a solid, forthright overview of the computer systems and management behind airline reservations? NASA's space shuttle? Or any of the multitude of other large computer systems that support important projects …

File organization: implementation of a method guaranteeing retrieval in one access

A new file organization method that guarantees retrieval of any record in one access is tested on two existing files, producing empirical results that compare favorably with theoretical predictions. The description of the method …

Audit trail compaction for database recovery

Total elapsed recovery time from disk-based database corruption can be shortened by reprocessing the audit trail off-line and thereby avoiding excessive resource utilization penalties. Using a bit map, the audit trail is compacted …

A null-object detection algorithm for constructive solid geometry

Constructive solid geometry (CSG) is the primary scheme used for representing solid objects in many contemporary solid modeling systems. A CSG representation is a binary tree whose nonterminal nodes represent Boolean operations …

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 …

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( …

Technical Correspondence—MEANSORT (April 1983): response from Dalia Motzkin with John Kapenga