\documentclass[12pt]{exam}

\usepackage[utf8]{inputenc}  % For UTF8 source encoding.
\usepackage{amsmath}  % For displaying math equations.
\usepackage{amsfonts} % For mathematical fonts (like \mathbb{E}!).
\usepackage{upgreek}  % For upright Greek letters, such as \upvarphi.
\usepackage{wasysym}  % For additional glyphs (like \smiley!).
\usepackage{mathrsfs} % For script text (hash families and universes).
% For document margins.
\usepackage[left=.8in, right=.8in, top=1in, bottom=1in]{geometry}
\usepackage{lastpage} % For a reference to the number of pages.

% TODO: Enter your name( here :)
\newcommand*{\authorname}{[Your name goes here]}

\newcommand*{\psetnumber}{4}
\newcommand*{\psetdescription}{Randomized Data Structures}
\newcommand*{\duedate}{Tuesday, May 11}
\newcommand*{\duetime}{2:30 PM Pacific}

% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2021}{Individual Assessment \psetnumber\\\psetdescription}{Due: \duedate\\at \duetime}
\runningheader{CS166}{Individual Assessment \psetnumber}{\authorname}
\footer{}{\footnotesize{Page \thepage\ of \pageref{LastPage}}}{}

% Exam questions.
\newcommand{\Q}[1]{\question{\large{\textbf{#1}}}}
\qformat{}  % Remove formatting from exam questions.

% Useful macro commands.
\newcommand*{\ex}{\mathbb{E}}
\newcommand*{\bigtheta}[1]{\Theta\left( #1 \right)}
\newcommand*{\bigo}[1]{O \left( #1 \right)}
\newcommand*{\bigomega}[1]{\Omega \left( #1 \right)}
\newcommand*{\prob}[1]{\text{Pr} \left[ #1 \right]}
\newcommand*{\var}[1]{\text{Var} \left[ #1 \right]}

\newcommand*{\RMQ}{\textrm{RMQ}}
\newcommand*{\RMQcomplexity}[2]{\left< #1, #2 \right>}

\newcommand*{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand*{\HH}{\mathscr{H}}   % Family of hash functions.
\newcommand*{\UU}{\mathscr{U}}   % Universe.
\newcommand*{\eps}{\varepsilon}  % Epsilon.

% Custom formatting for problem parts.
\renewcommand{\thepartno}{\roman{partno}}
\renewcommand{\partlabel}{\thepartno.}

% Framed answers.
\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{\fill}
\vspace{#1}
\end{framed}}

% MZ
\usepackage{amsthm}
\usepackage{amssymb}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\newcommand{\bi}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{stmaryrd}
\usepackage{pgfplots}
\pgfplotsset{compat=1.15}
\makeatletter
\@namedef{ver@framed.sty}{9999/12/31}
\@namedef{opt@framed.sty}{}
\makeatother
\usepackage{minted}
\usepackage{mathtools}
\usepackage{alltt}

\printanswers

\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}

\begin{document}
\title{CS166 Individual Assessment \psetnumber: \psetdescription}
\author{\authorname}
\date{}
\maketitle
\thispagestyle{headandfoot}

\begin{questions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem One: Cuckoo Hashing}

Here are two details about the implementation of vanilla cuckoo hashing (two hash functions, one item
per slot) that might seem challenging to handle in practice:
\begin{enumerate}
\item We need two hash functions $h_1(x)$ and $h_2(x)$ such that $h_1(x) \ne h_2(x)$ for any key $x$. It seems like it would be hard to get hash functions with these properties.
\item When displacing a key $x$ from its home, we need to move it to either position $h_1(x)$ or $h_2(x)$ depending on which of the two positions it was previously in. This seems like it requires us to compute $h_1(x)$ and $h_2(x)$ when doing the displacement, though one of those calculations isn’t needed.
\end{enumerate}

Turns out, there’s a really nice way to address both concerns.

Let’s begin by assuming that we have a table with m elements, where $m$ is a perfect power of two. We’ll assume we have access to two families of 2-independent hash functions: $\mathscr{H}_m$, which maps from the universe of keys to the set $\{0, 1, 2, \dots, m - 1\}$, and $\mathscr{H}_{m-1}$, which maps from the universe of keys to the set $\{1, 2, 3, \dots, m - 1\}$. We’ll then sample a hash function $h_1$ from $\mathscr{H}_m$ and a second hash function $h_\Delta$ from $\mathscr{H}_{m-1}$. We’ll then define our second hash function $h_2$ to be
\[h_2(x) = h_1(x) \oplus h_\Delta(x)\]
where $\oplus$ denotes the bitwise XOR operation.

\begin{parts}

\part Prove that $h_1(x) \ne h_2(x)$ for any key $x$

\begin{solution}
	Your solution goes here!
\end{solution}

\newpage

\uplevel{This choice of hash function makes it easy to displace an element from its current position to the position given by its other hash. Assuming we displace key $x$ from position $i$ in the table, we simply move key $x$ to position $i \oplus h_\Delta(x)$.}

\part Prove that this procedure always moves key $x$ from $h_1(x)$ to $h_2(x)$ or vice-versa.
\begin{solution}
Your solution goes here!
\end{solution}

\newpage

\uplevel{Now, let $\mathscr{H}_{cuckoo}$ denote the family of pairs of hash functions $(h_1, h_2)$ produced this way. This is a family of hash functions over the set $E = \{(i, j) | i, j \in [m] \text{ and } i \ne j\}$.}

\part Prove that $\mathscr{H}_{cuckoo}$ is 2-independent.
\begin{solution}
Your solution goes here!
\end{solution}
\end{parts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\Q{Problem Two: Final Details on Count Sketches}

In our analysis of count sketches from lecture, we made the following simplification when determining the variance of our estimate:
\[
	\var{\sum_{j \ne i}{\mathbf{a}_j s(x_i) s(x_j) X_j}} = \sum_{j \ne i}\var{\mathbf{a}_j s(x_i) s(x_j) X_j}
\]

In general, the variance of a sum of random variables is not the same as the sum of their variances. That only works in the case where all those random variables are \textbf{\textit{pairwise uncorrelated}}, as you saw on Problem Set Zero.

Prove that for any $j \ne k$ that $\mathbf{a}_j s(x_i) s(x_j) X_j$ and $\mathbf{a}_k s(x_i) s(x_k) X_k$ are pairwise uncorrelated random variables, under the assumption that both $s$ and $h$ are drawn uniformly and independently from separate 2-independent families of hash functions. Remember that $\mathbf{a}_j$ and $\mathbf{a}_k$ are not random variables. Two random variables $X$ and $Y$ are uncorrelated if $E[XY] = E[X]E[Y]$.

\begin{solution}
Your solution goes here!
\end{solution}

\end{questions}
\end{document}
