Sign In

Communications of the ACM

Table of Contents


ACM President's Letter: U.S. productivity in crisis


Best sorting algorithm for nearly sorted lists

Straight Insertion Sort, Shellsort, Straight Merge Sort, Quickersort, and Heapsort are compared on nearly sorted lists. The ratio of the minimum number of list elements which must be removed so that the remaining portion …

Bresenham's algorithm with Grey scale

The control parameter in Bresenham's algorithm, when interpreted as a measure of distance from a straight line boundary, gives a weighted average of the intensities on each side of the line. This can be used to produce an aesthetically …

Decentralized extrema-finding in circular configurations of processors

This note presents an efficient algorithm, requiring O(n log n) message passes, for finding the largest (or smallest) of a set of n uniquely numbered processors arranged in a circle, in which no central controller exists and  …

Design of a LISP-based microprocessor

We present a design for a class of computers whose “instruction sets” are based on LISP. LISP, like traditional stored-program machine languages and unlike most high-level languages, conceptually stores programs and data in the …

Disk scheduling: FCFS vs.SSTF revisited

We report on a rather extensive simulation effort directed at evaluating the merits of two scheduling strategies, FCFS and SSTF, for moving-arm disks under stationary request arrival process. For First-Come-First-Served (FCFS) …

ACM forum