**Rasterizing curves of constant width**

John D. Hobby

Pages: 209-229

DOI: 10.1145/62044.62045

This paper gives a fast, linear-time algorithm for generating high-quality pixel representations of curved lines. The results are similar to what is achieved by selecting a circle whose diameter is the desired line width, and turning on all...

**A model for concurrency in nested transactions systems**

Catriel Beeri, Philip A. Bernstein, Nathan Goodman

Pages: 230-269

DOI: 10.1145/62044.62046

Today's standard model for database concurrency control, called serializability theory, represents executions of transactions as partial orders of operations. The theory tells when an execution is serializable, that is, when the set of...

**Average case selection**

Walter Cunto, J. Ian Munro

Pages: 270-279

DOI: 10.1145/62044.62047

It is shown that n + k - O(1) comparisons are necessary, on average, to find the kth smallest of n numbers (k ⪇ n/2). This...

**On the path length of binary trees**

Rolf Klein, Derick Wood

Pages: 280-289

DOI: 10.1145/62044.62048

It is shown that the external path length of a binary tree is closely related to the ratios of means of certain integers and establish the upper bound ExternalPathLength≤N...

**Optimum combinations of sorting and merging**

G. K. Manacher, T. D. Bui, T. Mai

Pages: 290-334

DOI: 10.1145/62044.62049

In 1979, G. K. Manacher showed that the Ford-Johnson sorting algorithm [FJA], acting on t real numbers, can be beaten for an infinite set of values t. These values form a partial cover of constant density not...

**Efficient dispersal of information for security, load balancing, and fault tolerance**

Michael O. Rabin

Pages: 335-348

DOI: 10.1145/62044.62050

An Information Dispersal Algorithm (IDA) is developed that breaks a file F of length L = ↿ F↾ into n pieces Fi, l ≤...

**A generalized algorithm for centrality problems on trees**

Arnon Rosenthal, José A. Pino

Pages: 349-361

DOI: 10.1145/62044.62051

A general framework is presented for rapidly analyzing tree networks to compute a measure of the centrality or eccentricity of all vertices in the tree. Several problems, which have been previously described in...

**Size-time complexity of Boolean networks for prefix computations**

G. Bilardi, F. P. Preparata

Pages: 362-382

DOI: 10.1145/62044.62052

The prefix problem consists of computing all the products x0x1 … xj (j = 0, … , N -...

**Probabilistic inductive inference**

L. Pitt

Pages: 383-433

DOI: 10.1145/62044.62053

Inductive inference machines construct programs for total recursive functions given only example values of the functions. Probabilistic inductive inference machines are defined, and for various criteria of successful inference,...