Fixed Greek alphabetical order.

[saga.git] / ram.tex

diff --git a/ram.tex b/ram.tex
index 85118f166945f8a952c153c8dc305c819e9cf71e..9cd82445adc6d6a1b3a03e1da4bf0dc61290f516 100644 (file)
--- a/ram.tex
+++ b/ram.tex
@@ -9,7 +9,7 @@
 
 Traditionally, computer scientists use a~variety of computational models
 as a~formalism in which their algorithms are stated. If we were studying
 
 Traditionally, computer scientists use 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 the 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,
 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,


@@ -117,7 +117,7 @@ As for the choice of RAM operations, the following three instruction sets are of
 \:Both restrictions at once.
 \endlist
 
 \:Both restrictions at once.
 \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
 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


@@ -426,7 +426,7 @@ We will therefore manage with a~weaker form of equivalence, based on some sort
 of graph encodings:
 
 \defn
 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)
 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)


@@ -465,7 +465,7 @@ corresponding to all possible canonical encodings on $k$~vertices. Then we use u
 the \df{actual graphs} in~$\C$ to the generic graphs in~$\cal G$. This gives us the following
 theorem:
 
 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))$,
 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))$,


@@ -528,7 +528,7 @@ and expected $\O(n\sqrt{\log\log n})$ for randomized algorithms~\cite{hanthor:ra
 both in linear space.
 
 The Fusion trees themselves have very limited use in graph algorithms, but the
 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 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


@@ -607,7 +607,7 @@ for their encodings. The elements of a~vector~${\bf x}$ will be written as
 $x_0,\ldots,x_{d-1}$.
 
 \para
 $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
 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


@@ -923,8 +923,8 @@ 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.
 
 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
+Wherever 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
 of the original edges' labels.
 
 In both kinds of tries, we order the outgoing edges of every vertex by their labels


@@ -1002,7 +1002,7 @@ be efficiently precomputed. We will carefully choose an~equivalent representatio
 of the trie which is compact enough.
 
 \lemma\id{citree}%
 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
 
 \proof
 We already know that the letter depths of the trie vertices are exactly