The GCL ANSI Common Lisp Test Suite (2008)
I describe the conformance test suite for ANSI Common Lisp distributed as part of GNU Common Lisp (GCL). The test suite includes more than 20,000 individual tests, as well as random test generators...
Bits and Relative Order from Residues, Space Efficiently (1994)
Dietz, Paul F., Macarie, Ioan I., Seiferas, Joel I.
For each k, let P_k be the product of the first k primes. By the Chinese remainder theorem, each integer in the interval [0, P_k) is determined by its residues modulo these k primes. We address the...
A Tight Lower Bound for On-Line Monotonic List Labeling (1994)
Dietz, Paul F., Seiferas, Joel I., Zhang, Ju
Maintaining a monotonic labeling of an ordered list during the insertion of n items requires \Omega (n log n) individual relabelings in the worst case, if the number of usable labels is only...
A Tight Lower Bound for On-line Monotonic List Labeling (1994)
Paul F. Dietz, Joel I. Seiferas, Ju Zhang
. Maintaining a monotonic labeling of an ordered list during the insertion of n items requires\Omega (n log n) individual relabelings, in the worst case, if the number of usable labels is only...
Very Fast Optimal Parallel Algorithms for Heap Construction (1994)
We give two algorithms for permuting n items in an array into heap order on a CRCW PRAM. The first is deterministic and runs in O(log log n) time and performs O(n) operations. This run-time is the...
Bits and Relative Order from Residues, Space Efficiently (1994)
Paul F. Dietz, Ioan I. Macarie, Joel I. Seiferas
. For each k, let P k be the product of the first k primes. By the Chinese remainder theorem, each integer in the interval [0; P k ) is determined by its residues modulo these k primes. We address...
Heap Construction in the Parallel Comparison Tree Model (1992)
This paper shows how to put n values into heap order in O(log log n) time using n/log log n processors in the parallel comparison tree model of computation, and in O^~(\alpha(n)) time on n/\alpha(n)...
Finding Ancestors in Trees (1990)
from the Introduction: We examine the problem of answering ancestor queries on tree; that is, questions of the form "what is the ith ancestor of vertex v?" We solve this problem when the tree is...
Amortized Analysis of a Pebble Game (1990)
Dietz, Paul F., Sleator, Daniel D.
We consider the following one person game, motivated by the African games of Owari and Kalah.... [no abstract]
Elimination of Amortization from Breu's Algorithm (1989)
Breu [1] has given an algorithm for finding the maximum value between two pointers moving unidirectionally through an array. His algorithm achieves 0(1) amortized time per operation. This paper...
Optimal Algorithms for List Indexing and Subset Rank (1989)
Fredman and Saks [1] have proved a Ω(log n/ log log n) amortized time lower bound for two problems, List Indexing and Subset Rank, in the cell probe model with logarithmic word size. This paper...
Two Algorithms for Maintaining Order in a List (1989)
Dietz, Paul F., Sleator, Daniel D.
The order maintenance problem is that of maintaining a list under a sequence of Insert and Delete operations, while answering Order queries (determine which of two records comes first in the list)....
Two Algorithms for Maintaining Order in a List 1 (1988)
Daniel D. Sleator, Paul F. Dietz, Paul F. Dietz, Daniel D. Sleator
The order maintenance problem is that of maintaining a list under a se-quence of Insert and Delete operations, while answering Order queries (deter-mine which of two records comes first in the list)....
Intersection Graph Algorithms (1984)
An intersection graph for a set of sets $C$ is a graph $G$ together with a bijection from the vertices of $G$ to $C$ such that distinct vertices in $G$ are adjacent if and only if their images under...
Intersection Graph Algorithms (1984)
An intersection graph for a set of sets $C$ is a graph $G$ together with a bijection from the vertices of $G$ to $C$ such that distinct vertices in $G$ are adjacent if and only if their images under...
A Linear Time Algorithm for the Generalized Consecutive Retrieval Problem (1979)
Dietz, Paul F., Furst, Merrick, Hopcroft, John E.
THe Generalized Consecutive Retrieval Problem (GCRP) is to find a directed tree on $n$ records in which each of $k$ subsets forms a directed path. The problem arises in organizing information for...
A Linear Time Algorithm for the Generalized Consecutive Retrieval Problem (1979)
Dietz, Paul F., Furst, Merrick, Hopcroft, John E.
THe Generalized Consecutive Retrieval Problem (GCRP) is to find a directed tree on $n$ records in which each of $k$ subsets forms a directed path. The problem arises in organizing information for...