From f4a217d5daf9755e087e37c1b195c13abff71f65 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 14 Sep 2014 09:37:28 -0400
Subject: [ps1] a few more typos

---
 ps1/main.tex | 46 ++++++++++++++++++++++++++--------------------
 1 file changed, 26 insertions(+), 20 deletions(-)

(limited to 'ps1/main.tex')

diff --git a/ps1/main.tex b/ps1/main.tex
index 920cb3c..b04d730 100644
--- a/ps1/main.tex
+++ b/ps1/main.tex
@@ -42,7 +42,8 @@
 \paragraph{(a)} Statement (6) is wrong. The number of min pointers is not
 necessarily equal to the number of elements. Indeed, inserting an element can
 possibly require creating a min pointer in its cluster and recursively
-inserting its cluster id into the summary.
+inserting its cluster id into the summary, leading to more to than one min
+pointer for this element.
 
 \paragraph{(b)} See \textbf{(c)}.
 
@@ -70,15 +71,17 @@ We note that when inserting the first $\frac{\log u}{2}$ elements of $b(u)$, we
 will have to create one new cluster for each element and insert the cluster ids
 in the summary. But these cluster ids are exactly $b(\sqrt{u})$. The number of
 min pointers created during this phase is $S(\sqrt{u}) + \frac{\log u}{2}$.
+
 Then, inserting the last $\frac{\log u}{2}$ elements of $b(u)$ will lead to
-inserting $b(\sqrt{u})$ in a new cluster, whose id is 0, the number of min
-pointers created during this phase is $1 + S(\sqrt{u})$. Hence, the recursion
-takes the following form:
+inserting $b(\sqrt{u})$ in a new cluster whose id is 0, the number of min
+pointers created during this phase is $1 + S(\sqrt{u})$.
+
+Overall the number of min pointers created follows the recursion:
 \begin{displaymath}
     S(u) = 2S(\sqrt{u}) + 1 + \frac{\log u}{2}
 \end{displaymath}
 Solving it leads to $S(u) = \Omega(\log u\log\log u) = \Omega(n\log\log u)$.
-Since the space complexity of a $u$-vEB tree is equal the number of min
+Since the space complexity of a $u$-vEB tree is equal to the number of min
 pointers it contains, we have that the space complexity of the $u$-vEB tree
 containing $b(u)$ is $\Omega(n\log\log u)$.
 
@@ -170,13 +173,13 @@ following procedures:
         \begin{center}
             \texttt{perfect-sketch(x) := ((x * m) >> w) \& (1 << $\sqrt{\texttt{w}}$ - 1)}
         \end{center}
-    \item \texttt{count-ones}: takes a word of length $w$ whose bits are all $0$
-        except possibly the ones at position $i\sqrt{w} -1$, $1\leq i\leq
+    \item \texttt{count-ones}: takes a word of length $w$ whose bits are all
+        $0$ except possibly the ones at position $i\sqrt{w} -1$, $1\leq i\leq
         \sqrt{w}$ and counts the number of ones in this word. This is achieved
-        by multiplying $x$ by $a\eqdef\sum_{j=0}^{\sqrt{w}-1}2^j$. The number of ones
-        can be read between positions $w-1$ and $\sqrt{w}+w -2$ which can be
-        extracted by shifting by $w-1$ to the right and masking to keep only
-        the rightmost $\sqrt{w}$ bits.
+        by multiplying $x$ by $a\eqdef\sum_{j=0}^{\sqrt{w}-1}2^{j\sqrt{w}}$.
+        The number of ones can be read between positions $w-1$ and $\sqrt{w}+w
+        -2$ which can be extracted by shifting by $w-1$ to the right and
+        masking to keep only the rightmost $\sqrt{w}$ bits.
         \begin{center}
             \texttt{count-ones(x) := ((x * a) >> (w - 1)) \& (1 << $\sqrt{\texttt{w}}$ - 1)}
         \end{center}
@@ -188,7 +191,7 @@ following procedures:
         non-zero. This is achieved by defining $b\eqdef\sum_{j=1}^{\sqrt{w}}
         2^{j\sqrt{w}-1}$ and computing:
         \begin{center}
-            \texttt{non-empty-clusters(x) := (x \& b) | ( b $\wedge$ ( b \& ( b - ( x $\wedge$ ( x \& b))))) }
+            \texttt{non-empty-clusters(x) := (x \& b) | ( b $\wedge$ ( b \& ( b - ( x \& $\sim$b)))) }
         \end{center}
 
     \item \texttt{repeat}: takes a word $x$ of length $\sqrt{w}$ and returns a word
@@ -210,13 +213,12 @@ will consist of $\sqrt{w}$ clusters of length $\sqrt{w}$; the $k$-th rightmost
 cluster is empty if the rightmost $k$ bits of $x$ are all zero, that is, if the
 least significant bit of $x$ set to one is greater than or equal to $k$. Hence,
 the least significant bit of $x$ set to one is equal to the number of empty
-clusters in \texttt{repeat(x) \& c} which we can easily compute using
-a negation and the \texttt{non-empty-clusters} procedure. This allows us to
-define a procedure \texttt{lsb-short} which takes a word $x$ of length
-$\sqrt{w}$ and computes its least significant bit set to one:
+clusters in \texttt{repeat(x) \& c} which we can easily compute using the
+\texttt{non-empty-clusters} procedure. This allows us to define a procedure
+\texttt{lsb-short} which takes a word $x$ of length $\sqrt{w}$ and computes its
+least significant bit set to one:
 \begin{center}
-    \texttt{lsb-short(x) := count-ones($\sim$ non-empty-clusters(repeat(x) \&
-c)) - 1}
+    \texttt{lsb-short(x) := count-ones(b $\wedge$ non-empty-clusters(repeat(x) \& c))}
 \end{center}
 
 Then, the least significant bit set to one of a word $x$ of length $w$ can be
@@ -228,13 +230,17 @@ the least significant bit set to one in this cluster:
 
 \noindent\texttt{def lsb(x):}\newline
 \hspace*{1cm}\texttt{z := lsb-short(perfect-sketch(non-empty-clusters(x)))}\newline
-\hspace*{1cm}\texttt{if z == -1:}\newline
+\hspace*{1cm}\texttt{if z == $\sqrt{\texttt{w}}$:}\newline
 \hspace*{2cm}\texttt{return -1}\newline
-\hspace*{1cm}\texttt{return z * $\sqrt{\texttt{w}}$
+\hspace*{1cm}\texttt{else:}\newline
+\hspace*{2cm}\texttt{return z * $\sqrt{\texttt{w}}$
 + lsb-short((x >> z * $\sqrt{\texttt{w}}$) \& (1 << $\sqrt{\texttt{w}}$ - 1))}
 
+\vspace{1em}
+
 Note that the above code only requires a constant number of multiplications and
 bitwise operations once the constants $m$, $a$, $b$ and $c$ have been
 pre-computed.
 
+
 \end{document}
-- 
cgit v1.2.3-70-g09d2

