\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amsfonts,amsthm}
\usepackage[english]{babel}
\usepackage[capitalize, noabbrev]{cleveref}

% these are compressed lists to help fit into a 1 page limit
\newenvironment{enumerate*}%
  {\vspace{-2ex} \begin{enumerate} %
     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
  {\end{enumerate}}
 
\newenvironment{itemize*}%
  {\vspace{-2ex} \begin{itemize} %
     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
  {\end{itemize}}
 
\newenvironment{description*}%
  {\vspace{-2ex} \begin{description} %
     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
  {\end{description}}

\DeclareMathOperator*{\E}{\mathbb{E}}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbb{P}}

\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
\newcommand{\llbracket}{[\![}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\author{Thibaut Horel}
\title{CS 224 Problem Set 1 -- Solutions}

\begin{document}

\maketitle
\section*{Problem 1}

\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, leading to more to than one min
pointer for this element.

\paragraph{(b)} See \textbf{(c)}.

\paragraph{(c)} Let us denote by $N(u)$ the number of min pointers created when
inserting an element in a $u$-vEB tree. We have two cases:

\begin{itemize*}
    \item either a cluster already exists for that element, and then you just
        have to recusrively insert it in the cluster. In this case: $N(u)
        = N(\sqrt{u})$
    \item or you need to create a new cluster for this element (which creates
        one min pointer) and recursively insert the cluster id in the summary.
        In this case: $N(u) = 1 + N(\sqrt{u})$.
\end{itemize*}
In both cases, we have $N(u) \leq 1 + N(\sqrt{u})$. Solving this recursion
gives $N(u) = O(\log\log u)$ number of min-pointers per element, which
in turns gives a space complexity of $O(n\log\log u)$ for a $u$-vEB tree.

\paragraph{(d)} We give a family of examples for $n=\log u$, namely $b(u)$, the
first $\log(u)$ powers of two ($b(u)\eqdef (2^{\log{u}-1},\ldots, 4, 2,1)$. Let
us denote by $S(u)$ the number of min pointers created when inserting $b(u)$ in
a $u$-vEB tree.

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})$.

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 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)$.

\paragraph{(e)} We can use indirection to achieve linear space complexity as
follows:
\begin{enumerate*}
    \item order the $n$ elements and organize them in $\frac{n}{\log u}$
        buckets of $\log u$ consecutive elements.
    \item for each bucket, create a balanced binary search tree (a sorted
        array is enough in the static case) containing its elements.
    \item create a $u$-vEB tree containing $\frac{n}{\log u}$ elements: the
        minimum element of each bucket. Each of them pointing to its associated
        bucket.
\end{enumerate*}

We can then answer a predecessor query by:
\begin{enumerate*}
    \item finding the right bucket by doing a predecessor query in the $u$-vEB
        tree in time $O\left(\log\log\left(\frac{n}{\log u}\right)\right)$.
    \item finding the predecessor in this bucket (either using the
        binary search structure, or doing a binary search in the case of
        a sorted array) in time $O(\log\log u)$ since the bucket only contains
        $\log u$ elements.
\end{enumerate*}

Since $n\leq u$, the overall time complexity is $O(\log\log u)$. The space
complexity is $O\left(\frac{n}{\log u}\log\log u\right)$ for the $u$-vEB tree
and $O(n)$ for the binary search trees, which is $O(n)$ overall.

\section*{Problem 2}

Let us define:
\begin{displaymath}
    m\eqdef \sum_{j=1}^{\sqrt{w}} 2^{m_j} \quad\text{with}\quad
    m_j\eqdef w-j\sqrt{w} + j.
\end{displaymath}
We have:
\begin{equation}\label{eq:dec}
    y\eqdef\left(\sum_{i=1}^{\sqrt{w}} x_i 2^{i\sqrt{w}-1}\right)\times m
    = \sum_{i=1}^{\sqrt{w}}\sum_{j=1}^{\sqrt{w}} x_i 2^{m_j+i\sqrt{w} -1}
\end{equation}

\begin{lemma}\label{lemma:oto}
    The function $(i,j) \mapsto m_j + i\sqrt{w} -1$ defined on
    $\{1,\ldots,\sqrt{w}\}^2$ is one-to-one.
\end{lemma}

\begin{proof}
    Let us assume that $m_j + i\sqrt{w} - 1 = m_l + k\sqrt{w} - 1$ for
    $(i,j,k,l)\in\{1,\ldots,\sqrt{w}\}^4$. Then using the definiton of $m_j$
    and $m_l$, we have:
    \begin{displaymath}
        \big[(i-j) - (k-l)\big]\sqrt{w} = l-j.
    \end{displaymath}
    Since $1-\sqrt{w}\leq l-j\leq \sqrt{w}-1$, this implies that $l-j = 0$ and
    $(i-j) - (k-l) = 0$. This in turn implies that $i=k$ and $l=j$.
\end{proof}

\cref{lemma:oto} allows us to interpret \cref{eq:dec} as the base
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 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{
    m= \sum_{j=1}^{\sqrt{w}} 2^{w-j\sqrt{w}+j} \quad\text{and}\quad
t = w}
\end{displaymath}

\section*{Problem 3}

\paragraph{Second solution.}
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\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}
    \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 \& $\sim$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 rightmost block being equal
to $2^k-1$:
\begin{displaymath}
c\eqdef \sum_{k=1}^{\sqrt{w}} (2^k-1})2^{(k-1)\sqrt{w}}.
\end{displaymath} 

We note that if $x$ is a word of length $\sqrt{w}$, \texttt{repeat(x) \& c}
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 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(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
computed by first finding the rightmost non-empty cluster of length $\sqrt{w}$
in $x$, then extracting this cluster by shifting and masking, and then finding
the least significant bit set to one in this cluster:

\vspace{1em}

\noindent\texttt{def lsb(x):}\newline
\hspace*{1cm}\texttt{z := lsb-short(perfect-sketch(non-empty-clusters(x)))}\newline
\hspace*{1cm}\texttt{if z == $\sqrt{\texttt{w}}$:}\newline
\hspace*{2cm}\texttt{return -1}\newline
\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.

\paragraph{Alternative solution \emph{(too easy, felt like cheating).}} We saw in
class how to compute the most signigicant bit set to one. But observe that
\texttt{x \& $\sim$(x-1)} will clear all the bits of $x$ except for the least
significant bit set to one.  Assuming access to a procedure \texttt{msb} to
compute the most significant bit set to one, we can simply define
\texttt{lsb(x) $:=$ msb(x \& $\sim$(x-1))}.

\end{document}