1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
\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 229r 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, 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{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 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{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}
\end{document}
|
