Continuing with the intro to dynamic algorithms.

[saga.git] / rank.tex

diff --git a/rank.tex b/rank.tex
index c457a81d041fa150afa4ad63daa968d7ce3abcc9..a2b5ef6e7f4943f4471af44e1d62fe933df52507 100644 (file)
--- a/rank.tex
+++ b/rank.tex
@@ -3,6 +3,7 @@
 \fi
 
 \chapter{Ranking Combinatorial Structures}
+\id{rankchap}
 
 \section{Ranking and unranking}
 
@@ -246,7 +247,7 @@ and $\log n^{\underline k} \ge (n/2)(\log n - 1) \ge (k/2)(\log n - 1)$.
 It remains to show how to translate the operations on~$A$ to operations on~$H$,
 again stored as a~sorted vector~${\bf h}$. Insertion to~$A$ correspond to
 deletion from~$H$ and vice versa. The rank of any~$x\in[n]$ in~$A$ is $x$ minus
-the number of holes which are smaller than~$x$, therefore $R_A(x)=x-R_H(x)$.
+the number of holes that are smaller than~$x$, therefore $R_A(x)=x-R_H(x)$.
 To calculate $R_H(x)$, we can again use the vector operation \<Rank> from Algorithm \ref{vecops},
 this time on the vector~$\bf h$.
 
@@ -293,7 +294,7 @@ constant time. The time bound follows. \qed
 
 \section{Restricted permutations}
 
-Another interesting class of combinatorial objects which can be counted and
+Another interesting class of combinatorial objects that can be counted and
 ranked are restricted permutations. An~archetypal member of this class are
 permutations without a~fixed point, i.e., permutations~$\pi$ such that $\pi(i)\ne i$
 for all~$i$. These are also called \df{derangements} or \df{hatcheck permutations.}\foot{%
@@ -597,7 +598,7 @@ instead. We will show that for the derangements one can achieve linear time comp
 
 \nota\id{hatrank}%
 As we already know, the hatcheck permutations correspond to restriction
-matrices which contain zeroes only on the main diagonal and graphs which are
+matrices that contain zeroes only on the main diagonal and graphs that are
 complete bipartite with the matching $\{(i,i) : i\in[n]\}$ deleted. For
 a~given order~$n$, we will call this matrix~$D_n$ and the graph~$G_n$ and
 we will show that the submatrices of~$D_n$ share several nice properties:
@@ -671,7 +672,7 @@ We will count the permutations $\pi\in {\cal P}_d$ satisfying~$M_{z-1}$ in two w
 First, there are $n_0(z-1,d)$ such permutations. On the other hand, we can divide
 the them to two types depending on whether $\pi[1]=1$. Those having $\pi[1]\ne 1$
 are exactly the $n_0(z,d)$ permutations satisfying~$M_z$. The others correspond to
-permutations $(\pi[2],\ldots,\pi[d])$ on $\{2,\ldots,d\}$ which satisfy~$M_z^{1,1}$,
+permutations $(\pi[2],\ldots,\pi[d])$ on $\{2,\ldots,d\}$ that satisfy~$M_z^{1,1}$,
 so there are $n_0(z-1,d-1)$ of them.
 \qed
 
@@ -699,7 +700,7 @@ we have gained into the structure of derangements.
 The algorithm uses the matrix~$M$ only for computing~$N_0$ of its submatrices
 and we have shown that this value depends only on the order of the matrix and
 the number of zeroes in it. We will therefore replace maintenance of the matrix
-by remember the number~$z$ of its zeroes and the set~$Z$ which contains the elements
+by remember the number~$z$ of its zeroes and the set~$Z$ that contains the elements
 $x\in A$ whose locations are restricted (there is a~zero anywhere in the $(R_A(x)+1)$-th
 column of~$M$). In other words, every $x\in Z$ can appear at all positions in the
 permutation except one (and these forbidden positions are different for different~$x$'s),