\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage{dsfont}
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-8:\hspace{0.12cm}Advanced
          Algorithms (Spring'21)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{3: Hashing}{Jan 19,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Conor Sweeney (cjs2201), Erica Wei(cw3137)}}

\section{Course Info}
\begin{itemize}
\item Homework 1 has been posted (in courseworks under Files). It is due
  next Thursday Jan 28 at 4pm.
\item OH Calendar has been posted as well (see courseworks/course info
  for link).
\item Please sign up for to scribe (see courseworks announcement).
\end{itemize}

\section{Class Topics}
\textbullet{} 
Dictionary $\&$ Hashing  \\

\section{Problem: Dictionary}
In this problem, a dictionary, a data structure problem. We want to pre-process a subset S $\in$ U, U is a large universe, into the dictionary so that it can quickly answer if "Is x $\in$ S?" Solution is to use hashing.
\includegraphics[width=\textwidth]{dictionary.png}
Above is a visualization of how a dictionary maps a large universe U to a smaller easily search-able dictionary m.
\subsection{Collision}
When $x \neq y$, but hash function maps them into the same cell s.t $h(x) = h(y)$. 
\subsection{Ideal}
Enough for hash function h such that $\forall y \in S,  \forall x \in U, x \neq y \to h(x) \neq h(y)$.   
\subsection{Issue}
It is very hard to construct such a hash function because it depends on S a lot. And it is hard to compute the hash function. Here we will construct a hash function h s.t we have a better trade-off between computation/evaluation time and how "good" it is for distribution in terms of collisions. 

\section{Solutions}
\subsection{Random Function}
Randomly choose hash function h and allow some collisions. 

$H = \{\text{all functions } h : U \rightarrow \lfloor m \rfloor\}$

$|H| = m^{|u|}$

$h \in H$ is chosen at random

\subsubsection{So what is the size of each bucket?}

Let $C_{x}$ := the collision count for x then:

$C_{x} \triangleq $ the number of elements in S s.t. $h(x) = h(y)$\newline
\newline
Then the expectation for collisions can be considered as:
\begin{equation} 
\begin{split}
    \mathds{E}_{n}[\text{size of the bucket}] &= \mathds{E}[C_{x}]\\ 
    &= \mathds{E}_{n} [ \sum _{i \in S} \mathds{1} [ h(i) = h(x)]]\\
    &= \sum _{i \in S}  \mathds{E}_{n}[\mathds{1} [ h(i) = h(x)]] \\
    &= |s| \cdot \frac{1}{m}\\
    &= \frac{n}{m}
\end{split}
\end{equation}

It is OK to set $m = \Theta(n)$ (e.g. m = n) which would mean that $\mathds{E}_{n}[\text{size of the buckets}] = 1$.\newline
\newline
Query Time = $O(1)$ + time to compute h (in expectations)
\subsubsection{How large is the biggest bucket?}
$\Theta(\frac{log(n)}{log(log(n))})$ with probability at least 99\%.

\subsubsection{How do we choose/store the random hash function h?}
It is actually okay to use a hash function $h \in H$ with "less" randomness. See section 5.3 for more details.

\subsection{Knuth’s Solution}
Knuth suggests a concrete hash function to use:  
\begin{equation}
    h(x) = \lfloor \{ \frac{\sqrt{5} -1 }{2}x \} * m  \rfloor
\end{equation}
m is the integer where U maps to [m]. This is not a good hash function because it's deterministic and in some cases it will have a large number of collisions. 

\subsection{Less Random}
\textbf{Definition}: $H$ is $\alpha \cdot$ almost -universal if 
\begin{equation}
    \forall x \neq y, Pr_{h}(h(x) = h(y)) \leq \alpha / m 
\end{equation}
In this case we relax from randomness and the probability of collisions is upper bounded.  

\begin{claim}
$\E[\text{size of the bucket}] \leq \alpha \cdot n/m $.
\end{claim}
The proof is similar as above.\\
\textbf{Example [Dietzfelbinger et al., ’97] }: 
\begin{equation}
\begin{split}
    \forall a \in [U] \text{ a is randomly chosen with odd number}, \\ 
    h_a(x) = \lfloor (a \cdot x) \% | U | \cdot \frac{m}{|U|} \rfloor\\ 
    H = \{h_a, a \in [U] odd \}
\end{split}
\end{equation}
\\
\textbf{Fact}: H is 2-almost universal. 
\\
\textbf{Lemma}: Dictionary problem can be solved by using O(n) space and O(1) expected query time. 
\begin{proof}
Set m = n, table takes space O(m+n)= O(n), $E[\text{size of bucket}] \leq 1 + \frac{n}{m} = 2.$
Hash function description is $O(lg|U|)$. 
\end{proof}

\subsection{Perfect Hashing}
\textbf{Goal} O(1) run time deterministically.\\ 
\textbf{Ideally} Let $C \triangleq \sum_{x \in S} C_x$, 
we want C = 0 $\Rightarrow$ size of bucket $\leq$ 1. \\

\begin{equation}
\begin{split}
    \E[c] &= \E_h[ \sum_{x \in S} C_x ]  \\ 
          &= \sum_{x \in S} \E_h[ C_x ] \\ 
          &= \sum_{x \in S} n/ m \\ 
          &= \frac{n^2}{m}
\end{split}
\end{equation}
Suppose set m = 4$n^2$, then $\E[c] = 1/4$. \\ 
By Markov Bound: 
\begin{equation}
Pr[C \geq 4 \E [C]] \leq \frac{\E[C]}{4\E[C]} =\frac{1}{4}
\end{equation}
With probability at least 3/4, we have $C < 4\E[C] = 1 $. Since C is an integer, here we can say C = 0, no collisions. \\
\textbf{Corollary}: can solve Dictionary problem with $O(n^2)$ space and O(1) query time. \\
\\
Algorithm is following: \\
1) Set m = $4n^2$ \\ 
2) Build a hash table using a random hash function $h \in H$.\\ 
3) Compute C. \\ 
4) If C $\geq$ 1, then try again. \\ 
This will eventually finish because the probability you have to try again is 1/4. The idea here is the size of table is large enough so there's not many collisions. 
\\
\textbf{Issue}: How many times we need to try again?
\begin{equation}
    \begin{split}
        \E[ \text{\# of tries in pre-processing algorithm}] &= 1 \cdot 1 + 1/4 + (1/4)^2 + (1/4)^3 + ... \\ 
        \text{Another way to think about it is }
        &= 1 \cdot 3/4 + 1/4 \cdot (3/4) * 2 + (1/4)^2 \cdot (3/4)* 3 + ... \\ 
        &= \frac{1}{1- 1/4}  = 4/3 
    \end{split}
\end{equation}

Expectation to try is 4/3 times. 

\end{document}
