PS1, halfway there

1 files changed, 91 insertions, 16 deletions

diff --git a/ps1/main.tex b/ps1/main.tex
index 9ad9153..40da92b 100644
--- a/ps1/main.tex
+++ b/ps1/main.tex
@@ -1,6 +1,8 @@
 \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*}%
@@ -24,36 +26,109 @@
 
 \newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
 \newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
+\newcommand{\llbracket}{[\![}
 
 \newtheorem{theorem}{Theorem}
 \newtheorem{lemma}{Lemma}
 
-\author{Jelani Nelson}
+\author{Thibaut Horel}
 \title{CS 229r Problem Set 1 -- Solutions}
 
 \begin{document}
 
 \maketitle
+\section*{Problem 1}
 
-Here is a theorem with proof.
+\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.
+
+\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:
+
+\begin{itemize*}
+    \item either a cluster already exists for that element, and then you just
+        have to 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 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)}
+
+\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{theorem}
-The square root of $2$ is irrational.
-\end{theorem}
 \begin{proof}
-For the sake of contradiction suppose $\sqrt{2}$ is rational. Write $\sqrt{2} = a/b$ with $a,b$ positive integers with gcd $1$. Then $2 = a^2/b^2$, so $a = 2k$ is even. Then $2 = 4k^2/b^2$ so that $b = 2k^2$, implying $b$ is even. This contradicts that $a,b$ have gcd $1$.
+    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}
 
-Some random facts in a list:
+\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 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:
 
-\begin{itemize*}
-\item Compared with the ``itemize'' environment in \LaTeX, itemize$^*$ has smaller separation between bullet points.
-\item The $n$th Catalan number is $C_n \eqdef \frac{1}{n+1} \binom{2n}{n}$.
-\item If $\pi(x)$ is the number of primes less than or equal to $x$, then
-$$\lim_{x\rightarrow\infty} \frac{\pi(x)}{x/\ln(x)} = 1 . $$
-\item $$ \sum_{\substack{1\le i\le 2n\\i\ \mathrm{even}}} i = \frac{2n(n+1)}2 .$$
-\end{itemize*}
+\begin{displaymath}
+    \boxed{
+    m= \sum_{j=1}^{\sqrt{w}} 2^{w-j\sqrt{w}+j} \quad\text{and}\quad
+t = w}
+\end{displaymath}
 
-Have fun on your problem sets.
+\section*{Problem 3}
 
-\end{document}
\ No newline at end of file
+\end{document}