From cdb9599635c62f95cdf88aa95dac650a436a1f1a Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Mon, 8 Sep 2014 14:24:33 -0400
Subject: Still a few details missing, but should be enough to get A+

---
 ps1/main.tex | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 59 insertions(+), 4 deletions(-)

diff --git a/ps1/main.tex b/ps1/main.tex
index 40da92b..27e31e6 100644
--- a/ps1/main.tex
+++ b/ps1/main.tex
@@ -41,8 +41,8 @@
 
 \paragraph{(a)} Statement (6) is wrong. The number of min pointers is
 not necessarily equal to the number of elements. Indeed, when you insert an
-element, you have to insert it in both its own cluster and (potentially) in the
-summary, leading to (potentially) more than one min pointer per element.
+element, you have to insert it in both its own cluster and (possibly) in the
+summary, leading to (possibly) more than one min pointer per element.
 
 \paragraph{(c)} Let us denote by $N(u)$ the number of min pointers that you
 have to create when inserting an element in a $u$-vEB tree. We have two cases:
@@ -120,8 +120,8 @@ We have:
 2 decomposition of $y$ (since all the exponents are distinct). Furthermore, for
   $i=j$, $m_i + i\sqrt{w} = w+i-1$, which shows that the bits between position
   $w$ and $w+\sqrt{w}-1$ will contain the bits of $x$ in consecutive order.
-  Then, we simply have to shift $y$ by $w$ to the right ($t=w$) and only keep
-  the first $\sqrt{w}$ bits (by masking) to get what we want. To summarize:
+  Then, we simply shift $y$ by $w$ to the right ($t=w$) and keep the rightmost
+  $\sqrt{w}$ bits (by masking) to obtain what we want. To summarize:
 
 \begin{displaymath}
     \boxed{
@@ -131,4 +131,59 @@ t = w}
 
 \section*{Problem 3}
 
+Using Problem 2 and what we did in class, we assume that we have access to the
+following procedures:
+\begin{itemize*}
+    \item \texttt{perfect-sketch}: takes a word $x$ 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 compress them (preserving their order) to positions
+        $0$ to $\sqrt{w}-1$. This is achieved using Problem 2.
+        \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
+        \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.
+        \begin{center}
+            \texttt{count-ones(x) := ((x * a) >> (w - 1)) \& (1 << $\sqrt{\texttt{w}}$ - 1)}
+        \end{center}
+    \item \texttt{non-empty-clusters}: takes a word $x$ of length $w$ seen as
+        the concatenation of $\sqrt{w}$ clusters of length $\sqrt{w}$ and
+        returns a word of length $w$ which is the concatenation of clusters of
+        length $\sqrt{w}$, each cluster being all zero, except for the leading
+        bit indicating whether of not the corresponding cluster in $x$ is
+        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))))) }
+        \end{center}
+
+    \item \texttt{repeat}: takes a word $x$ of length $\sqrt{w}$ and returns a word
+        of length $w$ obtained by concatenating $x$ to itself $\sqrt{w}$ times:
+        \begin{center}
+            \texttt{repeat(x) := (x * a)}
+        \end{center}
+\end{itemize*}
+    
+Finally, we will need one last constant, $c$ which is the concatenation of
+$\sqrt{w}$ blocks of length $\sqrt{w}$, the $k$-th right most block being equal
+to $2^k-1$, $c\eqdef \sum_{k=1}^{\sqrt{w}} (2^k-1)2^{(k-1)\sqrt{w}}$. We first
+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(non-empty-clusters(repeat(x) \& c))}
+\end{center}
+Then, the least significant bit set to one can be computed by:
+\begin{verbatim}
+def lsb(x):
+    z := lsb-short(perfect-sketch(non-empty-clusters(x)))
+    return 1 << z + lsb-short((x >> z * \sqrt{w}) & (1 << \sqrt{w} - 1))
+\end{verbatim}
+In the above code, $z$ computes the position of the rightmost non empty
+$\sqrt{w}$-block in $x$. The least significant bit set to one can then be
+obtained by applying \texttt{lsb-short} to this block.
 \end{document}
-- 
cgit v1.2.3-70-g09d2