October 1988 - Vol. 31 No. 10
Features
Along the twists and turns of this year's presidential campaign trails, computers act as strategic tools that exert a decisive impact on capturing voters' attention. But a National Bureau of Standards study claims that system implementations are dangerously inadequate at the finish line, where carefully gleaned votes are less carefully counted.
Accuracy, integrity and security in computerized vote-tallying
The following excerpts have been gleaned from a 130-page report of potential inaccuracies and fraud in computerized voting systems. Recent difficulties in automated vote-tallying, including specific legal cases, are detailed along with a summary of conclusions and recommendations.
Random number generators: good ones are hard to find
Practical and theoretical issues are presented concerning the design, implementation, and use of a good, minimal standard random number generator that will port to virtually all systems.
Characterizing computer performance with a single number
The controversy surrounding single number performance reduction is examined and solutions are suggested through a comparison of measures.
Probabilistic and genetic algorithms in document retrieval
Document retrieval systems are built to provide inquirers with computerized access to relevant documents. Such systems often miss many relevant documents while falsely identifying many non-relevant documents. Here, competing document descriptions are associated with a document and altered over time by a genetic algorithm according to the queries used and relevance judgments made during retrieval.
Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem
A new priority queue implementation for the future event set problem is described in this article. The new implementation is shown experimentally to be O(1) in queue size for the priority increment distributions recently considered by Jones in his review article. It displays hold times three times shorter than splay trees for a queue size of 10,000 events. The new implementation, called a calendar queue, is a very simple structure of the multiple list variety using a novel solution to the overflow problem.
A subset coloring algorithm and its applications to computer graphics
We consider the following problem: we are given a diagram made up of intersecting circles, where each region is colored either black or white. We wish to display this diagram on a bitmap device, where we are allowed to (i) paint a given circle white and (ii) invert the colors within a given circle, changing white to black and vice versa. (These operations are frequently provided in graphics hardware or software.) We ask: using only these paint and invert operations, is it possible to draw the diagram? A generalization of this problem leads to an analogous coloring problem on a subset of the power set of n elements. We give a polynomial-time algorithm that answers the question above, and produces a "short" sequence of instructions to draw the diagram, if one exists. A simple modification of the algorithm permits us to handle the case where there are more colors than just black and white, and the colors are represented by bit strings. This corresponds to the conventions frequently used with color raster devices.
