Home → Magazine Archive → November 1980 (Vol. 23, No. 11)
Table of Contents
ACM President's Letter: U.S. productivity in crisis
Peter J. Denning
Pages 617-619
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 …
Curtis R. Cook, Do Jin Kim
Pages 620-624
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 …
M. L. V. Pitteway, D. J. Watkinson
Pages 625-626
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
…
D. S. Hirschberg, J. B. Sinclair
Pages 627-628
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 …
Guy Lewis Steele, Gerald Jay Sussman
Pages 628-645
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) …
Micha Hofri
Pages 645-653
ACM forum
Robert L. Ashenhurst
Pages 659-660