\section{Models and machines}
-Traditionally, computer scientists use a~variety of computational models
+Traditionally, computer scientists have been using a~variety of computational models
as a~formalism in which their algorithms are stated. If we were studying
-NP-completeness, we could safely assume that all the models are equivalent,
+NP-complete\-ness, we could safely assume that all these models are equivalent,
possibly up to polynomial slowdown which is negligible. In our case, the
differences between good and not-so-good algorithms are on a~much smaller
scale. In this chapter, we will replace the usual ``tape measure'' by a~micrometer,
state our computation models carefully and develop a repertoire of basic
-data structures taking advantage of the fine details of the models.
+data structures tailor-made for the fine details of the models.
We would like to keep the formalism close enough to the reality of the contemporary
computers. This rules out Turing machines and similar sequentially addressed
time to access a~single element of an~$n$-element array. It is hard to say which
way is superior --- while most ``real'' computers have instructions for constant-time
indexing, it seems to be physically impossible to fulfil this promise regardless of
-the size of memory. Indeed, at the level of logical gates inside the computer,
+the size of addressable memory. Indeed, at the level of logical gates inside the computer,
the depth of the actual indexing circuits is logarithmic.
In recent decades, most researchers in the area of combinatorial algorithms
\para
The \df{Random Access Machine (RAM)} is not a~single coherent model, but rather a~family
-of closely related machines, sharing the following properties.
+of closely related machines which share the following properties.
(See Cook and Reckhow \cite{cook:ram} for one of the usual formal definitions
and Hagerup \cite{hagerup:wordram} for a~thorough description of the differences
between the RAM variants.)
The \df{memory} of the machine is represented by an~array of \df{memory cells}
-addressed by non-negative integers, each of them containing a~single non-negative integer.
+addressed by non-negative integers. Each cell contains a~single non-negative integer.
The \df{program} is a~finite sequence of \df{instructions} of two basic kinds: calculation
instructions and control instructions.
counting not only the values, but also the addresses of the respective memory
cells.
\:Place a~limit on the size of the numbers ---define the \df{word size~$W$,}
- the number of bits available in the memory cells--- and keep the cost of
+ the number of bits available in each memory cell--- and keep the cost of
instructions and memory cells constant. The word size must not be constant,
since we can address only~$2^W$ cells of memory. If the input of the algorithm
is stored in~$N$ cells, we need~$W\ge\log N$ just to be able to read the input.
fan-in and fan-out. This includes all operations of the Word-RAM except for multiplication,
division and remainders, and also many other operations like computing the Hamming
weight (number of bits set in a~given number).
-\:Both restrictions at once.
+\:Both restrictions combined.
\endlist
-Thorup discusses the usual techniques employed by RAM algorithms in~\cite{thorup:aczero}
+Thorup \cite{thorup:aczero} discusses the usual techniques employed by RAM algorithms
and he shows that they work on both Word-RAM and ${\rm AC}^0$-RAM, but the combination
of the two restrictions is too weak. On the other hand, the intersection of~${\rm AC}^0$
with the instruction set of modern processors is already strong enough (e.g., when we
When speaking of the \df{RAM,} we implicitly mean the version with numbers limited
by a~specified word size of $W$~bits, unit cost of operations and memory cells and the instruction
set of the Word-RAM. This corresponds to the usage in recent algorithmic literature,
-although the authors rarely mention the details. In some cases, a~non-uniform variant
-of the Word-RAM is considered as well (e.g., in~\cite{hagerup:dd}):
+although the authors rarely mention the details.
+
+In some cases, a~non-uniform variant
+of the Word-RAM is considered as well (e.g., by Hagerup \cite{hagerup:dd}):
\defn\id{nonuniform}%
A~Word-RAM is called \df{weakly non-uniform,} if it is equipped with $\O(1)$-time
access to a~constant number of word-sized constants, which depend only on the word
size. These are called \df{native constants} and they are available in fixed memory
cells when the program starts. (By analogy with the high-level programming languages,
-these constants can be thought of as computed at ``compile time.'')
+these constants can be thought of as computed at ``compile time''.)
\para
-The \df{Pointer Machine (PM)} also does not have any well established definition. The
-various kinds of pointer machines are mapped by Ben-Amram in~\cite{benamram:pm},
+The \df{Pointer Machine (PM)} also does not seem to have any well established definition. The
+various kinds of pointer machines are examined by Ben-Amram in~\cite{benamram:pm},
but unlike the RAM's they turn out to be equivalent up to constant slowdown.
Our definition will be closely related to the \em{linking automaton} proposed
by Knuth in~\cite{knuth:fundalg}, we will only adapt it to use RAM-like
The PM works with two different types of data: \df{symbols} from a~finite alphabet
and \df{pointers}. The memory of the machine consists of a~fixed amount of \df{registers}
(some of them capable of storing a~single symbol, each of the others holds a~single pointer)
-and an~arbitrary amount of \df{cells}. The structure of all cells is the same: each of them
+and an~arbitrary amount of \df{cells}. The structure of all cells is the same: each cell
again contains a~fixed number of fields for symbols and pointers. Registers can be addressed
directly, the cells only via pointers --- by using a~pointer stored either in a~register,
-or in a~cell pointed to by a~register (longer chains of pointers cannot be followed in
-constant time).
+or in a~cell pointed to by a~register. Longer chains of pointers cannot be followed in
+constant time.
We can therefore view the whole memory as a~directed graph, whose vertices
correspond to the cells (the registers are stored in a~single special cell).
The outgoing edges of each vertex correspond to pointer fields of the cells and they are
labeled with distinct labels drawn from a~finite set. In addition to that,
-each vertex contains a~fixed amount of symbols. The program can directly access
+each vertex contains a~fixed amount of symbols. The machine can directly access
vertices within distance~2 from the register vertex.
The program is a~finite sequence of instructions of the following kinds:
\itemize\ibull
\:\df{symbol instructions,} which read a~pair of symbols, apply an~arbitrary
- function on them and write the result to a~symbol register or field;
+ function to them and write the result to a~symbol register or field;
\:\df{pointer instructions} for assignment of pointers to pointer registers/fields
- and for creation of new memory cells (a~pointer to the new cell is assigned
+ and for creation of new memory cells (a~pointer to the new cell is stored into a~register
immediately);
\:\df{control instructions} --- similarly to the RAM; conditional jumps can decide
- on~arbitrary unary relations on symbols and compare pointers for equality.
+ arbitrary unary relations on symbols and compare pointers for equality.
\endlist
Time and space complexity are defined in the straightforward way: all instructions
and arithmetic instructions. We can emulate both with poly-logarithmic slowdown,
but it will turn out that they are rarely needed in graph algorithms. We are
also going to prove that the RAM is strictly stronger, so we will prefer to
-formulate our algorithms in the PM model and use RAM only when necessary.
+formulate our algorithms for the PM and use the RAM only when necessary.
\thm
Every program for the Word-RAM with word size~$W$ can be translated to a~PM program
\para
There are also \df{randomized} versions of both machines. These are equipped
with an~additional instruction for generating a~single random bit. The standard
-techniques of design and analysis of randomized algorithms apply (see for
+methods of design and analysis of randomized algorithms can be used (see for
example Motwani and Raghavan~\cite{motwani:randalg}).
\rem
-There is one more interesting machine: the \df{Immutable Pointer Machine} (see
+There is one more interesting machine: the \df{Immutable Pointer Machine} (mentioned for example in
the description of LISP machines in \cite{benamram:pm}). It differs from the
ordinary PM by the inability to modify existing memory cells. Only the contents
of the registers are allowed to change. All cell modifications thus have to
persistent --- it is possible to return to a~previously visited state by recalling
the $\O(1)$ values of the registers (everything else could not have changed
since that time) and ``fork'' the computations. This corresponds to the semantics
-of pure functional languages, e.g., Haskell~\cite{jones:haskell}.
+of pure functional languages, e.g., of Haskell~\cite{jones:haskell}.
Unless we are willing to accept a~logarithmic penalty in execution time and space
(in fact, our emulation of the Word-RAM on the PM can be easily made immutable),
the design of efficient algorithms for the immutable PM requires very different
-techniques. Therefore, we will concentrate on the imperative models instead
+techniques. Therefore, we will be interested in the imperative models only
and refer the interested reader to the thorough treatment of purely functional
data structures in the Okasaki's monograph~\cite{okasaki:funcds}.
\paran{Flattening on RAM}%
On the RAM, we can view the edges as ordered pairs of vertex identifiers with the
-smaller of the identifiers placed first and sort them lexicographically. This brings
+smaller of the identifiers placed first. We sort these pairs lexicographically. This brings
parallel edges together, so that a~simple linear scan suffices to find each bunch
-of parallel edges and remove all but the lightest one.
+of parallel edges and to remove all but the lightest one.
Lexicographic sorting of pairs can be accomplished in linear time by a~two-pass
bucket sort with $n$~buckets corresponding to the vertex identifiers.
-However, there is a~catch in this. Suppose that we use the standard representation
+However, there is a~catch. Suppose that we use the standard representation
of graphs by adjacency lists whose heads are stored in an array indexed by vertex
identifiers. When we contract and flatten the graph, the number of vertices decreases,
but if we inherit the original vertex identifiers, the arrays will still have the
adjacency list. However, we have to find a~way how to perform bucket sorting
without indexing of arrays.
-We will keep a~list of the per-vertex structures that defines the order of~vertices.
+We will keep a~list of the per-vertex structures and we will use it to establish the order of~vertices.
Each such structure will be endowed with a~pointer to the head of the list of items in
the corresponding bucket. Inserting an~edge to a~bucket can be then done in constant time
and scanning the contents of all~$n$ buckets takes $\O(n+m)$ time.
compare the identifiers only for equality. We can work around this again by bucket-sorting:
we sort the multiset $\{ (x,i) \mid \hbox{$x$~occurs in the $i$-th pair} \}$ on~$x$.
Then we reset all pairs and re-insert the values back in their increasing order.
-This is also $\O(n+m)$.
+This also takes $\O(n+m)$.
\paran{Tree isomorphism}%
Another nice example of pointer-based radix sorting is a~Pointer Machine algorithm for
of both trees by their depth. This can be accomplished by running depth-first search to calculate
the depths and bucket-sorting them with $n$~buckets afterwards.
-Then we proceed from depth~0 to the maximum depth and for each of them we identify
-the isomorphism equivalence classes of subtrees of that particular depth. We will assign
-unique identifiers all such classes; at most~$n+1$ of them are needed as there are
+Then we proceed from depth~0 to the maximum depth and for each depth we identify
+the isomorphism equivalence classes of the particular subtrees. We will assign
+unique \df{codes} (identifiers) to all such classes; at most~$n+1$ of them are needed as there are
$n+1$~subtrees in the tree (including the empty subtree). As the PM does not
-have numbers as a~first-class type, we create a~``\df{yardstick}'' ---a~list
+have numbers as an~elementary type, we create a~``\df{yardstick}'' ---a~list
of $n+1$~distinct items--- and we use pointers to these ``ticks'' as identifiers.
When we are done, isomorphism of the whole trees can be decided by comparing the
-identifiers assigned to their roots.
+codes assigned to their roots.
Suppose that classes of depths $0,\ldots,d-1$ are already computed and we want
to identify those of depth~$d$. We will denote their count of~$n_d$. We take
-a~root of every such tree and label it with an~ordered $k$-tuple of identifiers
+a~root of every such tree and label it with an~ordered $k$-tuple of codes
of its subtrees; when it has less than $k$ sons, we pad the tuple with empty
subtrees. Tuples corresponding to isomorphic subtrees are identical up to
reordering of elements. We therefore sort the codes inside each tuple and then
If we are not careful, a~single sorting pass takes $\O(n_d + n)$ time, because
while we have only $n_d$~items to sort, we have to scan all $n$~buckets. This can
-be easily avoided if we realize that the order of buckets does not need to be
+be easily avoided if we realize that the order of the buckets does not need to be
fixed --- in every pass, we can use a~completely different order and it still
does bring the equivalent tuples together. Thus we can keep a~list of buckets
-which are used in the current pass and look only inside these buckets. This way,
+that are used in the current pass and look only inside these buckets. This way,
we reduce the time spent in a~single pass to $\O(n_d)$ and the whole algorithm
-takes $\O(\sum_d n_d) = \O(n)$.
+takes just $\O(\sum_d n_d) = \O(n)$.
Our algorithm can be easily modified for trees with unrestricted degrees.
-We replace the fixed $d$-tuples by general sequences of identifiers. The first
+We replace the fixed $d$-tuples by general sequences of codes. The first
sort does not need any changes. In the second sort, we proceed from the first
position to the last one and after each bucket-sorting pass we put aside the sequences
that have just ended. They are obviously not equivalent to any other sequences.
-The second sort is linear in the sum of the lengths of the sequences, which is
+The time complexity of the second sort is linear in the sum of the lengths of the sequences, which is
$n_{d+1}$ for depth~$d$. We can therefore decide isomorphism of the whole trees
in time $\O(\sum_d (n_d + n_{d+1})) = \O(n)$.
The first linear-time algorithm that partitions all subtrees to isomorphism equivalence
classes is probably due to Zemlayachenko \cite{zemlay:treeiso}, but it lacks many
details. Dinitz et al.~\cite{dinitz:treeiso} have recast this algorithm in modern
-terminology and filled the gaps. Our algorithm is easier to formulate than those,
+terminology and filled the gaps. Our algorithm is easier to formulate,
because it replaces the need for auxiliary data structures by more elaborate bucket
sorting.
separately inside these ``micrographs'' and in the ``macrograph'' obtained by
contraction of the micrographs. If $k$~is small enough, many of the micrographs
are isomorphic, so we can compute the result only once for each isomorphism class
-and recycle it for all micrographs in that class. On the other hand, the macrograph
+and recycle it for all micrographs of that class. On the other hand, the macrograph
is roughly $k$~times smaller than the original graph, so we can use a~less efficient
algorithm and it will still run in linear time with respect to the size of the original
graph.
(cf.~Alstrup et al.~\cite{alstrup:marked}). Let us take a~glimpse at what happens when
we decompose a~tree with $k$ set to~$1/4\cdot\log n$. There are at most $2^{2k} = \sqrt n$ non-isomorphic subtrees of size~$k$,
because each isomorphism class is uniquely determined by the sequence of $2k$~up/down steps
-performed by depth-first search. Suppose that we are able to decompose the input and identify
+performed by depth-first search of the tree. Suppose that we are able to decompose the input and identify
the equivalence classes of microtrees in linear time, then solve the problem in time $\O(\poly(k))$ for
each microtree and finally in $\O(n'\log n')$ for the macrotree of size $n'=n/k$. When we put these pieces
together, we get an~algorithm for the whole problem which achieves time complexity $\O(n
+ \sqrt{n}\cdot\poly(\log n) + n/\log n\cdot\log(n/\log n)) = \O(n)$.
Decompositions are usually implemented on the RAM, because subgraphs can be easily
-encoded in numbers, which can be then used to index arrays containing the precomputed
+encoded in numbers, and these can be then used to index arrays containing the precomputed
results. As the previous algorithm for subtree isomorphism shows, indexing is not strictly
required for identifying equivalent microtrees and it can be replaced by bucket
sorting on the Pointer Machine. Buchsbaum et al.~\cite{buchsbaum:verify} have extended
Let us define them.
\defn
-A~\df{graph computation} is a~function that takes a~\df{labeled undirected graph} as its input. The labels of its
+A~\df{graph computation} is a~function that takes a~\df{labeled undirected graph} as its input. The labels of
vertices and edges can be arbitrary symbols drawn from a~finite alphabet. The output
of the computation is another labeling of the same graph. This time, the vertices and
edges can be labeled with not only symbols of the alphabet, but also with pointers to the vertices
The topological graph computations cover a~great variety of graph problems, ranging
from searching for matchings or Eulerian tours to finding Hamilton circuits.
The MST problem itself however does not belong to this class, because we do not have any means
-of representing the edge weights as labels, unless of course there is only a~fixed amount
+of representing the edge weights as labels, unless there is only a~fixed amount
of possible values.
As in the case of tree decompositions, we would like to identify the equivalent subgraphs
of graph encodings:
\defn
-A~\df{canonical encoding} of a~given labeled graph represented by adjancency lists
+A~\df{canonical encoding} of a~given labeled graph represented by adjacency lists
is obtained by running the depth-first search on the graph and recording its traces.
We start with an~empty encoding. When we enter
a~vertex, we assign an~identifier to it (again using a~yardstick to represent numbers)
on~$n$ vertices with $m$~edges is assigned an~encoding of length at most $2n+2m$ ---
for each vertex, we record its label and a~single terminator; edges contribute
by identifiers and labels. These encodings can be constructed in linear time and
-in the same time we can also create a~graph corresponding to any encoding.
+in the same time we can also create a~graph corresponding to a~given encoding.
We will use the encodings for our unification of graphs:
\defn
the \df{actual graphs} in~$\C$ to the generic graphs in~$\cal G$. This gives us the following
theorem:
-\thmn{Batched topological computations, Buchsbaum et al.~\cite{buchsbaum:verify}}\id{topothm}%
+\thmn{Topological computations, Buchsbaum et al.~\cite{buchsbaum:verify}}\id{topothm}%
Suppose that we have a~topological graph computation~$\cal T$ that can be performed in time
$T(k)$ for graphs on $k$~vertices. Then we can run~$\cal T$ on a~collection~$\C$
of labeled graphs on~$k$ vertices in time $\O(\Vert\C\Vert + (k+s)^{k(k+2)}\cdot (T(k)+k^2))$,
take advantage of both indexing and arithmetics and they often surpass the known
lower bounds for the same problem on the~PM. In many cases, they achieve constant time
per operation, at least when either the magnitude of the values or the size of
-the data structure are suitably bounded.
+the data structure is suitably bounded.
-A~classical result of this type are the trees of van Emde Boas~\cite{boas:vebt}
-which represent a~subset of the integers $\{0,\ldots,U-1\}$. They allow insertion,
+A~classical result of this type is the tree of van Emde Boas~\cite{boas:vebt}
+which represent a~subset of the integers $\{0,\ldots,U-1\}$. It allows insertion,
deletion and order operations (minimum, maximum, successor etc.) in time $\O(\log\log U)$,
regardless of the size of the subset. If we replace the heap used in the Jarn\'\i{}k's
algorithm (\ref{jarnik}) by this structure, we immediately get an~algorithm
for finding the MST in integer-weighted graphs in time $\O(m\log\log w_{max})$,
where $w_{max}$ is the maximum weight.
-A~real breakthrough has been however made by Fredman and Willard who introduced
+A~real breakthrough has however been made by Fredman and Willard who introduced
the Fusion trees~\cite{fw:fusion}. They again perform membership and predecessor
operation on a~set of $n$~integers, but with time complexity $\O(\log_W n)$
per operation on a~Word-RAM with $W$-bit words. This of course assumes that
each element of the set fits in a~single word. As $W$ must at least~$\log n$,
the operations take $\O(\log n/\log\log n)$ time and thus we are able to sort $n$~integers
in time~$o(n\log n)$. This was a~beginning of a~long sequence of faster and
-faster sorting algorithms, culminating with the work by Thorup and Han.
+faster sorting algorithms, culminating with the work of Thorup and Han.
They have improved the time complexity of integer sorting to $\O(n\log\log n)$ deterministically~\cite{han:detsort}
and expected $\O(n\sqrt{\log\log n})$ for randomized algorithms~\cite{hanthor:randsort},
both in linear space.
The Fusion trees themselves have very limited use in graph algorithms, but the
-principles behind them are ubiquitious in many other data structures and these
+principles behind them are ubiquitous in many other data structures and these
will serve us well and often. We are going to build the theory of Q-heaps in
Section \ref{qheaps}, which will later lead to a~linear-time MST algorithm
for arbitrary integer weights in Section \ref{iteralg}. Other such structures
will help us in building linear-time RAM algorithms for computing the ranks
of various combinatorial structures in Chapter~\ref{rankchap}.
-Outside our area, important consequences of these data structures include the
+Outside our area, important consequences of RAM data structures include the
Thorup's $\O(m)$ algorithm for single-source shortest paths in undirected
graphs with positive integer weights \cite{thorup:usssp} and his $\O(m\log\log
n)$ algorithm for the same problem in directed graphs \cite{thorup:sssp}. Both
Another approach to division is using the improved elementary school algorithm as described
by Knuth in~\cite{knuth:seminalg}. It uses $\O(k^2)$ steps, but the steps involve
calculation of the most significant bit set in a~word. We will show below that it
-can be done in constant time, but we have to be careful to avoid division instructions.
+can be done in constant time, but we have to be careful to avoid division instructions in it.
\qed
\notan{Bit strings}\id{bitnota}%
\notan{Vectors}\id{vecnota}%
We will use boldface letters for vectors and the same letters in normal type
-for their encodings. The elements of a~vector~${\bf x}$ will be written as
+for the encodings of these vectors. The elements of a~vector~${\bf x}$ will be written as
$x_0,\ldots,x_{d-1}$.
\para
-If we want to fit the whole vector in a~single word, the parameters $b$ and~$d$ must satisty
+If we want to fit the whole vector in a~single word, the parameters $b$ and~$d$ must satisfy
the condition $(b+1)d\le W$.
By using multiple-precision arithmetics, we can encode all vectors satisfying $bd=\O(W)$.
We will now describe how to translate simple vector manipulations to sequences of $\O(1)$ RAM operations
-on their codes. As we are interested in asymptotic complexity only, we prefer clarity
-of the algorithms over saving instructions. Among other things, we freely use calculations
+on their codes. As we are interested in asymptotic complexity only, we will prefer clarity
+of the algorithms over saving instructions. Among other things, we will freely use calculations
on words of size $\O(bd)$, assuming that the Multiple-precision lemma comes to save us
when necessary.
\itemize\ibull
-\:$\<Replicate>(\alpha)$ --- creates a~vector $(\alpha,\ldots,\alpha)$:
+\:$\<Replicate>(\alpha)$ --- Create a~vector $(\alpha,\ldots,\alpha)$:
\alik{\<Replicate>(\alpha)=\alpha\cdot(\0^b\1)^d. \cr}
-\:$\<Sum>(x)$ --- calculates the sum of the elements of~${\bf x}$, assuming that
+\:$\<Sum>(x)$ --- Calculate the sum of the elements of~${\bf x}$, assuming that
the result fits in $b$~bits:
\alik{\<Sum>(x) = x \bmod \1^{b+1}. \cr}
\[r_{d-1}] \dd \[r_2] \[r_1] \[s_d] \dd \[s_3] \[s_2] \[s_1] \cr
}
-This way, we even get the vector of all partial sums:
+This way, we also get the vector of all partial sums:
$s_k=\sum_{i=0}^{k-1}x_i$, $r_k=\sum_{i=k}^{d-1}x_i$.
-\:$\<Cmp>(x,y)$ --- element-wise comparison of~vectors ${\bf x}$ and~${\bf y}$,
-i.e., a~vector ${\bf z}$ such that $z_i=1$ if $x_i<y_i$ and $z_i=0$ otherwise.
+\:$\<Cmp>(x,y)$ --- Compare vectors ${\bf x}$ and~${\bf y}$ element-wise,
+i.e., make a~vector~${\bf z}$ such that $z_i=1$ if $x_i<y_i$ and $z_i=0$ otherwise.
We replace the separator zeroes in~$x$ by ones and subtract~$y$. These ones
change back to zeroes exactly at the positions where $x_i<y_i$ and they stop
It only remains to shift the separator bits to the right positions, negate them
and mask out all other bits.
-\:$\<Rank>(x,\alpha)$ --- returns the number of elements of~${\bf x}$ which are less than~$\alpha$,
+\:$\<Rank>(x,\alpha)$ --- Return the number of elements of~${\bf x}$ which are less than~$\alpha$,
assuming that the result fits in~$b$ bits:
\alik{
\<Rank>(x,\alpha) = \<Sum>(\<Cmp>(x,\<Replicate>(\alpha))). \cr
}
-\:$\<Insert>(x,\alpha)$ --- inserts~$\alpha$ into a~sorted vector $\bf x$:
+\:$\<Insert>(x,\alpha)$ --- Insert~$\alpha$ into a~sorted vector $\bf x$:
-We calculate the rank of~$\alpha$ in~$x$ first, then we insert~$\alpha$ as the $k$-th
+We calculate the rank of~$\alpha$ in~$x$ first, then we insert~$\alpha$ into the particular
field of~$\bf x$ using masking operations and shifts.
\algo
\:$k\=\<Rank>(x,\alpha)$.
-\:$\ell\=x \band \1^{(b+1)(n-k-1)}\0^{(b+1)(k+1)}$. \cmt{``left'' part of the vector}
+\:$\ell\=x \band \1^{(b+1)(n-k)}\0^{(b+1)k}$. \cmt{``left'' part of the vector}
\:$r=x \band \1^{(b+1)k}$. \cmt{``right'' part}
\:Return $(\ell\shl (b+1)) \bor (\alpha\shl ((b+1)k)) \bor r$.
\endalgo
-\:$\<Unpack>(\alpha)$ --- creates a~vector whose elements are the bits of~$\(\alpha)_d$.
-In other words, inserts blocks~$\0^b$ between the bits of~$\alpha$. Assuming that $b\ge d$,
+\:$\<Unpack>(\alpha)$ --- Create a~vector whose elements are the bits of~$\(\alpha)_d$.
+In other words, insert blocks~$\0^b$ between the bits of~$\alpha$. Assuming that $b\ge d$,
we can do it as follows:
\algo
\:$x\=\<Replicate>(\alpha)$.
\:$y\=(2^{b-1},2^{b-2},\ldots,2^0)$. \cmt{bitwise encoding of this vector}
\:$z\=x \band y$.
-\:Return $\<Cmp>(z,y)$.
+\:Return $\<Cmp>(z,y) \bxor (\0^b\1)^d$.
\endalgo
Let us observe that $z_i$ is either zero or equal to~$y_i$ depending on the value
of the $i$-th bit of the number~$\alpha$. Comparing it with~$y_i$ normalizes it
-to either zero or one.
+to either zero or one, but in the opposite way than we need, so we flip the bits
+by an~additional $\bxor$.
-\:$\<Unpack>_\pi(\alpha)$ --- like \<Unpack>, but changes the order of the
+\:$\<Unpack>_\pi(\alpha)$ --- Like \<Unpack>, but change the order of the
bits according to a~fixed permutation~$\pi$: The $i$-th element of the
resulting vector is equal to~$\alpha[\pi(i)]$.
Implemented as above, but with a~mask $y=(2^{\pi(b-1)},\ldots,2^{\pi(0)})$.
-\:$\<Pack>(x)$ --- the inverse of \<Unpack>: given a~vector of zeroes and ones,
-it produces a~number whose bits are the elements of the vector (in other words,
+\:$\<Pack>(x)$ --- The inverse of \<Unpack>: given a~vector of zeroes and ones,
+produce a~number whose bits are the elements of the vector (in other words,
it crosses out the $\0^b$ blocks).
We interpret the~$x$ as an~encoding of a~vector with elements one bit shorter
\endlist
-\para
+\paran{Scalar operations}%
We can use the aforementioned tricks to perform interesting operations on individual
numbers in constant time, too. Let us assume for a~while that we are
operating on $b$-bit numbers and the word size is at least~$b^2$.
\itemize\ibull
-\:$\<Weight>(\alpha)$ --- computes the Hamming weight of~$\alpha$, i.e., the number of ones in~$\(\alpha)$.
+\:$\<Weight>(\alpha)$ --- Compute the Hamming weight of~$\alpha$, i.e., the number of ones in~$\(\alpha)$.
We perform \<Unpack> and then \<Sum>.
-\:$\<Permute>_\pi(\alpha)$ --- shuffles the bits of~$\alpha$ according
+\:$\<Permute>_\pi(\alpha)$ --- Shuffle the bits of~$\alpha$ according
to a~fixed permutation~$\pi$.
We perform $\<Unpack>_\pi$ and \<Pack> back.
-\:$\<LSB>(\alpha)$ --- finds the least significant bit of~$\alpha$,
+\:$\<LSB>(\alpha)$ --- Find the least significant bit of~$\alpha$,
i.e., the smallest~$i$ such that $\alpha[i]=1$.
By a~combination of subtraction with $\bxor$, we create a~number
Then we calculate the \<Weight> of the result and subtract~1.
-\:$\<MSB>(\alpha)$ --- finds the most significant bit of~$\alpha$ (the position
+\:$\<MSB>(\alpha)$ --- Find the most significant bit of~$\alpha$ (the position
of the highest bit set).
Reverse the bits of the number~$\alpha$ first by calling \<Permute>, then apply \<LSB>
\endlist
-\rem
+\paran{LSB and MSB}%
As noted by Brodnik~\cite{brodnik:lsb} and others, the space requirements of
-the \<LSB> operation can be reduced to linear. We split the input to $\sqrt{b}$
-blocks of $\sqrt{b}$ bits each. Then we determine which blocks are non-zero and
+the \<LSB> operation can be lowered to linear. We split the $w$-bit input to $\sqrt{w}$
+blocks of $\sqrt{w}$ bits each. Then we determine which blocks are non-zero and
identify the lowest such block (this is a~\<LSB> of a~number whose bits
correspond to the blocks). Finally we calculate the \<LSB> of this block. In
-both calls to \<LSB,> we have a $\sqrt{b}$-bit number in a~$b$-bit word, so we
-can use the previous algorithm. The same trick of course works for finding the
-\<MSB> as well.
+both calls to \<LSB,> we have a $\sqrt{w}$-bit number in a~$w$-bit word, so we
+can use the previous algorithm. The same trick of course applies to for finding the
+\<MSB>, too.
The following algorithm shows the details.
\algo\id{lsb}
\algin A~$w$-bit number~$\alpha$.
-\:$b\=\lceil\sqrt{w}\,\rceil$. \cmt{size of a~block}
+\:$b\=\lceil\sqrt{w}\,\rceil$. \cmt{the size of a~block}
\:$\ell\=b$. \cmt{the number of blocks is the same}
-\:$x\=(\alpha \band (\0\1^b)^\ell) \bor (\alpha \band (\1\0^b)^\ell)$.
+\:$x\=(\alpha \band (\0\1^b)^\ell) \bor ((\alpha \band (\1\0^b)^\ell) \shr 1)$.
\hfill\break
\cmt{encoding of a~vector~${\bf x}$ such that $x_i\ne 0$ iff the $i$-th block is non-zero}%
\foot{Why is this so complicated? It is tempting to take $\alpha$ itself as a~code of this vector,
-but we unfortunately need the separator bits between elements, so we create them and
+but we must not forget the separator bits between elements, so we create them and
relocate the bits we have overwritten.}
\:$y\=\<Cmp>(0,x)$. \cmt{$y_i=1$ if the $i$-th block is non-zero, otherwise $y_0=0$}
\:$\beta\=\<Pack>(y)$. \cmt{each block compressed to a~single bit}
\algout $\<LSB>(\alpha) = bp+q$.
\endalgo
-\rem
+\paran{Constants}%
We have used a~plenty of constants that depend on the format of the vectors.
Either we can write non-uniform programs (see \ref{nonuniform}) and use native constants,
or we can observe that all such constants can be easily manufactured. For example,
-$(\0^b\1)^d = \1^{(b+1)d} / \1^{b+1} = (2^{(b+1)d}-1)/(2^{b+1}-1)$. The only exceptions
+$(\0^b\1)^d = \1^{(b+1)d} / \1^{b+1} = (2^{(b+1)d}-1)/(2^{b+1}-1) = ((1 \shl (b+1)d)-1) / ((2\shl b) - 1)$. The only exceptions
are the~$w$ and~$b$ in the LSB algorithm \ref{lsb}, which we are unable to produce
in constant time. In practice we use the ``bit tricks'' as frequently called subroutines
-in an~encompassing algorithm, so we usually can spend a~lot of time on the precalculation
+in an~encompassing algorithm, so we usually can afford spending a~lot of time on the precalculation
of constants performed once during algorithm startup.
-\rem
+\paran{History}%
The history of combining arithmetic and logical operations to obtain fast programs for various
-interesting functions is blurred. Many of the ``bit tricks'' we have described have been
+interesting functions is blurred. Many of the bit tricks, which we have described, have been
discovered independently by numerous people in the early ages of digital computers.
Since then, they have become a~part of the computer science folklore. Probably the
earliest documented occurrence is in the 1972's memo of the MIT Artificial Intelligence
The exponential-time preprocessing may sound alarming, but a~typical application uses
Q-heaps of size $k=\log^{1/4} N$, where $N$ is the size of the algorithm's input.
This guarantees that $k\le W^{1/4}$ and $\O(2^{k^4}) = \O(N)$. Let us however
-remark that the whole construction is primarily of theoretical importance
-and that the huge constants involved everywhere make these heaps useless
-in practical algorithms. Despise this, many of the tricks we develop have proven
-themselves useful even in real-life implementations.
+remark that the whole construction is primarily of theoretical importance ---
+the huge multiplicative constants hidden in the~$\O$ make these heaps useless
+in practical algorithms. Despite this, many of the tricks we develop have proven
+themselves useful even in real-life data structures.
-Spending the time on reprocessing makes it possible to precompute tables for
-almost arbitrary functions and then assume that they can be evaluated in
+Spending so much time on preprocessing makes it possible to precompute tables of
+almost arbitrary functions and then assume that the functions can be evaluated in
constant time:
\lemma\id{qhprecomp}%
\qed
\paran{Tries and ranks}%
-We will first show an~auxiliary construction based on tries and then derive
+We will first develop an~auxiliary construction based on tries and then derive
the real definition of the Q-heap from it.
\nota
-Let us introduce some notation first:
\itemize\ibull
\:$W$ --- the word size of the RAM,
\:$k = \O(W^{1/4})$ --- the limit on the size of the heap,
indexed in a~way that $x_1 < \ldots < x_n$,
\:$g_i = \<MSB>(x_i \bxor x_{i+1})$ --- the position of the most significant bit in which $x_i$ and~$x_{i+1}$ differ,
\:$R_X(x)$ --- the rank of~$x$ in~$X$, that is the number of elements of~$X$ which are less than~$x$
-(where $x$~itself need not be an~element of~$X$).\foot{We will dedicate the whole chapter \ref{rankchap} to the
+(where $x$~itself need not be an~element of~$X$).\foot{We will dedicate the whole Chapter~\ref{rankchap} to the
study of various ranks.}
\endlist
a~rooted tree whose vertices are the prefixes of the strings in~$S$ and there
is an~edge going from a~prefix~$\alpha$ to a~prefix~$\beta$ iff $\beta$ can be
obtained from~$\alpha$ by appending a~single symbol of the alphabet. The edge
-will be labeled with the particular symbol. We will also define the~\df{letter depth}
+will be labeled with that particular symbol. We will also define the~\df{letter depth}
of a~vertex as the length of the corresponding prefix. We mark the vertices
which match a~string of~$S$.
-A~\df{compressed trie} is obtained from the trie by removing the vertices of outdegree~1
-except for the root and marked vertices.
-Whereever is a~directed path whose internal vertices have outdegree~1 and they carry
-no mark, we replace this path by a~single edge labeled with the contatenation
+A~\df{compressed trie} is obtained by removing the vertices of outdegree~1
+except for the root and the marked vertices.
+Wherever there is a~directed path whose internal vertices have outdegree~1 and they carry
+no mark, we replace this path by a~single edge labeled with the concatenation
of the original edges' labels.
In both kinds of tries, we order the outgoing edges of every vertex by their labels
lexicographically.
\obs
-In both tries, the root of the tree is the empty word and for every other vertex, the
-corresponding prefix is equal to the concatenation of edge labels on the path
+In both tries, the root of the tree is the empty word. Generally, the prefix
+in a~vertex is equal to the concatenation of edge labels on the path
leading from the root to that vertex. The letter depth of the vertex is equal to
the total size of these labels. All leaves correspond to strings in~$S$, but so can
some internal vertices if there are two strings in~$S$ such that one is a~prefix
of the other.
Furthermore, the labels of all edges leaving a~common vertex are always
-distinct and when we compress the trie, no two such labels have share their initial
+distinct and when we compress the trie, no two such labels share their initial
symbols. This allows us to search in the trie efficiently: when looking for
a~string~$x$, we follow the path from the root and whenever we visit
an~internal vertex of letter depth~$d$, we test the $d$-th character of~$x$,
For our set~$X$, we define~$T$ as a~compressed trie for the set of binary
encodings of the numbers~$x_i$, padded to exactly $W$~bits, i.e., for $S = \{ \(x)_W \mid x\in X \}$.
+\float{\valign{\vfil#\vfil\cr
+\hbox{\epsfbox{pic/qheap.eps}}\cr
+\noalign{\qquad\quad}
+ \halign{#\hfil&\quad#\hfil\cr
+ $x_1 = \0\0\0\0\1\1$ & $g_1=3$ \cr
+ $x_2 = \0\0\1\0\1\0$ & $g_2=4$ \cr
+ $x_3 = \0\1\0\0\0\1$ & $g_3=2$ \cr
+ $x_4 = \0\1\0\1\0\1$ & $g_4=5$ \cr
+ $x_5 = \1\0\0\0\0\0$ & $g_5=0$ \cr
+ $x_6 = \1\0\0\0\0\1$ \cr
+ }\cr
+}}{Six numbers stored in a~compressed trie}
+
\obs
The trie~$T$ has several interesting properties. Since all words in~$S$ have the same
length, the leaves of the trie correspond to these exact words, that is to the numbers~$x_i$.
-The inorder traversal of the trie enumerates the words of~$S$ in lexicographic order
+The depth-first traversal of the trie enumerates the words of~$S$ in lexicographic order
and therefore also the~$x_i$'s in the order of their values. Between each
pair of leaves $x_i$ and~$x_{i+1}$ it visits an~internal vertex whose letter depth
is exactly~$W-1-g_i$.
of the trie which is compact enough.
\lemma\id{citree}%
-The trie is uniquely determined by the order of the guides~$g_1,\ldots,g_{n-1}$.
+The compressed trie is uniquely determined by the order of the guides~$g_1,\ldots,g_{n-1}$.
\proof
We already know that the letter depths of the trie vertices are exactly
must lie in the left subtree of the root and $x_{i+1},\ldots,x_n$ in its
right subtree. Both subtrees can be then constructed recursively.\foot{This
construction is also known as the \df{cartesian tree} for the sequence
-$g_1,\ldots,g_n$ and it is useful in many other algorithms as it can be
+$g_1,\ldots,g_{n-1}$ and it is useful in many other algorithms as it can be
built in $\O(n)$ time. A~nice application on the Lowest Common Ancestor
and Range Minimum problems has been described by Bender et al.~in \cite{bender:lca}.}
\qed
\obs\id{qhsetb}%
The set~$B$ has $\O(k\log W)=\O(W)$ bits, so it can be stored in a~constant number
-of machine words in form of a~sorted vector. The function~$G$ can be also stored as a~vector
+of machine words in the form of a~sorted vector. The function~$G$ can be also stored as a~vector
of $\O(k\log k)$ bits. We can change a~single~$g_i$ in constant time using
vector operations: First we delete the original value of~$g_i$ from~$B$ if it
is not used anywhere else. Then we add the new value to~$B$ if it was not
The relation between $x$ and~$x_i$ can be obtained directly as we know the~$x_i$.
The bit position of the first disagreement can be calculated in constant time
-using the LSB/MSB algorithm (\ref{lsb}).
+using the Brodnik's LSB/MSB algorithm (\ref{lsb}).
All these ingredients can be stored in $\O(k\log k)$ bits, so we may assume
that the rank can be looked up in constant time as well.
\qed
\para
-In the Q-heap we would like to store the set~$X$ as a~sorted array together
+We would like to store the set~$X$ as a~sorted array together
with the corresponding trie, which will allow us to determine the position
for a~newly inserted element in constant time. However, the set is too large
to fit in a~vector and we cannot perform insertion on an~ordinary array in
constant time. This can be worked around by keeping the set in an~unsorted
-array together with a~vector containing the permutation that sorts the array.
+array and storing a~separate vector containing the permutation that sorts the array.
We can then insert a~new element at an~arbitrary place in the array and just
update the permutation to reflect the correct order.
+\paran{The Q-heap}%
We are now ready for the real definition of the Q-heap and for the description
of the basic operations on it.
\cite{thorup:aczero}). On the Word-RAM, we need to make use of the fact
that the set~$B$ is not changing too much --- there are $\O(1)$ changes
per Q-heap operation. As Fredman and Willard have shown, it is possible
-to maintain a~``decoder'', whose state is stored in $\O(1)$ machine words,
+to maintain a~``decoder'', whose state is stored in $\O(1)$ machine words
and which helps us to extract $x[B]$ in a~constant number of operations:
\lemman{Extraction of bits}\id{qhxtract}%
Actually, this is the only place where we need~$k$ to be as low as $W^{1/4}$.
In the ${\rm AC}^0$ implementation, it is enough to ensure $k\log k\le W$.
On the other hand, we need not care about the exponent because it can
-be arbitrarily increased using the Q-heap trees described below.}
+be increased arbitrarily using the Q-heap trees described below.}
it is possible to maintain a~data structure for a~set~$B$ of bit positions,
which allows~$x[B]$ to be extracted in $\O(1)$ time for an~arbitrary~$x$.
When a~single element is inserted to~$B$ or deleted from~$B$, the structure
\paran{Combining Q-heaps}%
We can also use the Q-heaps as building blocks of more complex structures
like Atomic heaps and AF-heaps (see once again \cite{fw:transdich}). We will
-show a~simpler, but useful construction, sometimes called the \df{Q-heap tree.}
+show a~simpler, but often sufficient construction, sometimes called the \df{Q-heap tree.}
Suppose we have a~Q-heap of capacity~$k$ and a~parameter $d\in{\bb N}^+$. We
can build a~balanced $k$-ary tree of depth~$d$ such that its leaves contain
a~given set and every internal vertex keeps the minimum value in the subtree
projects / saga.git / blobdiff