\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}{5}
\newcommand*{\psetdescription}{Randomized Data Structures}
\newcommand*{\duedate}{Thursday, May 28}
\newcommand*{\duetime}{2:30 PM Pacific}

% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2020}{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: Perfect Hash Functions}

Let's imagine we want to hash a fixed set of $n \ge 2$ distinct elements $x_1, x_2, \dots, x_n$ into a table with some hash function $h$. We’ll say that $h$ is a \textit{\textbf{perfect hash function}} for those elements if all the hash codes are distinct. That is, $h$ is a perfect hash function if $h(x_i) \ne h(x_j)$ whenever $i \ne j$.

Suppose that $h$ is a uniformly-random choice of a hash function from a 2-independent family of hash functions mapping from some universe $\UU$ to the set $[n^2]$. Your goal is to prove the following statement:

\textbf{\textit{Theorem:}}
There is a constant $p \in (0, 1)$, independent of $n$, such that $$Pr[h \mbox{ is a perfect hash function}] \ge p.$$

Let's begin by seeing an \textit{incorrect} argument that this is the case.

\begin{solution}
\textbf{\textit{Incorrect Proof}}: Consider any distinct $n \ge 2$ elements $x_1, x_2, ..., x_n$ drawn from $\UU$. We note that $h$ is a perfect hash function precisely if each item's hash code is different from the preceding items' hash codes. Since $h$ is drawn from a 2-independent family of hash functions, the probability that this occurs is given by

$$Pr[h \mbox{ is perfect}] = (\frac{n^2}{n^2}) \cdot (\frac{n^2 - 1}{n^2}) \cdot (\frac{n^2 - 2}{n^2}) \cdot \dots \cdot \cdot (\frac{n^2 - n + 1}{n^2}).$$

The first term follows since $h(x_1)$ can be any of the $n^2$ possible options, the hash code $h(x_2)$ can be any of the $n^2$ possible items except for the one selected as $h(x_1)$, the hash code $h(x_3)$ can be any of the $n^2$ possible items except for the two selected as $h(x_1)$ and $h(x_2)$, etc.

Each term in this product is at least $\frac{n^2 - n}{n^2}$ so we can lower-bound this expression as

$$\prod_{i=1}^n{(\frac{n^2 - n}{n^2})} = \prod_{i=1}^n{1 - \frac{1}{n}} = (1 - \frac{1}{n})^n$$

We note that the expression $(1 - \frac{1}{n})^n$ approaches $e^{-1}$ for large $n$, and is always at least $\frac{1}{4}$ in the case where $n \ge 2$. In particular, this means that

$$Pr[h \mbox{ is a perfect hash function}] \ge \frac{1}{4}.$$

Thus we see that $h$ is perfect with probability at least $\frac{1}{4}$, as required.
\end{solution}

This is a clever argument, but unfortunately it’s incorrect.

\begin{parts}

\part What's wrong with this proof? Point to a specific claim that's made that is incorrect or unsupported, then explain why it's incorrect or unsupported. (As a note, the claim about $(1 - \frac{1}{n})^n$ is correct, so that’s not the issue.)

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

\newpage
\part Write a correct proof of the theorem.
\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 any two terms in the above summation are uncorrelated under the assumption that both $s$ and $h$ are drawn uniformly and independently from separate 2-independent families of hash functions.

As a refresher, two random variables $X$ and $Y$ are uncorrelated if $\ex[XY] = \ex[X]\ex[Y]$.

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

\end{questions}
\end{document}
