diff options
| -rw-r--r-- | ps1/main.tex | 107 |
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} |