diff options
| -rw-r--r-- | ps1/main.tex | 46 |
1 files changed, 26 insertions, 20 deletions
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} |