Fixed Greek alphabetical order.

[saga.git] / ram.tex

diff --git a/ram.tex b/ram.tex
index 165e66d139edea0c740d5ded01814d0f16be8c08..9cd82445adc6d6a1b3a03e1da4bf0dc61290f516 100644 (file)
--- a/ram.tex
+++ b/ram.tex
@@ -426,7 +426,7 @@ We will therefore manage with a~weaker form of equivalence, based on some sort
 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)
@@ -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
-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
@@ -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
-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
@@ -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.
-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