%Template based off AMS Dept HW class file v0.05 by Eric Harley
\documentclass{article}

\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{amssymb,amsmath,amsthm,amsfonts,mathtools}
\usepackage{hyperref}
\usepackage{fullpage}
\usepackage{url}
\usepackage{listings}
\usepackage[utf8]{inputenc}
\usepackage{boxedminipage}
\usepackage{enumerate}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}

\newenvironment{problem}{%
  \bigskip\noindent\begin{boxedminipage}{\columnwidth}%
}{\end{boxedminipage}}

\newenvironment{solution}{%
  \begin{trivlist}\item[]%
}{%
  \mbox{}\penalty10000\hfill\ensuremath{\scriptscriptstyle\blacksquare}%
  \end{trivlist}%
}

\begin{document}

\begin{flushright}
Your name\\
CS 261, Spring 2021\\
Homework 2\\
Due Monday, April 12
\end{flushright}

\begin{problem}
\textbf{1.}
Give pseudocode for a subroutine that takes as input a sequence of items (represented in a way that allows the subroutine to loop through the items) and produces as output a dictionary with the items as keys and with the number of times each item occurs as a value. For instance, for the input \verb|("a", "b", "a", "c")| the output should be the dictionary (in Python syntax) \verb|{"a": 2, "b": 1, "c": 1}|. In your pseudocode, you should access the dictionary only through the operations listed on the ``Dictionary API'' slide of the lecture notes; do not make up new dictionary operations that are not listed on that slide.
\end{problem}

\begin{solution}
% YOUR SOLUTION TO PROBLEM 1 GOES HERE
\end{solution}

\begin{problem}
\textbf{2.}
Suppose we are using hash chaining for a set of $n$ keys, mapped by a random hash function to a hash table with exactly $n$ cells. Write a formula, as a function of $n$, for the probability that the first cell is empty, and evaluate your formula numerically for $n=1000$ to four decimal digits of precision.
\end{problem}

\begin{solution}
% YOUR SOLUTION TO PROBLEM 2 GOES HERE
\end{solution}

\begin{problem}
\textbf{3.}
Starting from the cuckoo hash table shown on the lecture note slide ``Graph view of cuckoo state'', describe the sequence of operations that would be performed if we insert a new key $K$ with value $5$, $h_1(K)=3$, and $h_2(K)=1$, and show what the graph view of the hash table looks like after the insertion is complete. Which of the cases listed in the slide ``Graph view of key insertion'' describes this insertion?
\end{problem}

\begin{solution}
% YOUR SOLUTION TO PROBLEM 3 GOES HERE
\end{solution}

\begin{problem}
\textbf{4.}
This problem is about how to distinguish a random hash function $r(x)$ from a function $f_2(x)$ described by the algebraic method for $k$-independence, with $k=2$. If $x$ and $g$ are integers, then we say that the triple of numbers $(x,x+g,x+2g)$ is an \emph{arithmetic progression}. We will test whether a hash function $h$ is random or whether it is 2-independent by selecting a random progression $(x,y,z)$ and testing whether $(h(x),h(y),h(z))$ is also an arithmetic progression. We want to prove that this test succeeds (that is, that the result is another arithmetic progression) with much larger probability for $f_2$ than for $r$.

\smallskip
(a) Let $M$ be a fixed positive integer. Suppose we choose $x$ and $g$ uniformly at random modulo $M$, and construct the triple $(x,(x+g)\bmod M, (x+2g)\bmod M)$. Here, the mod $M$ operation is defined to always return an integer between $0$ and $M-1$ (inclusive). The resulting triple might or might not be an arithmetic progression when considered as integers (not modulo $M$). For instance, with $M=5$, $x=g=1$ gives the triple $(1,2,3)$, which is an arithmetic progression, but $x=g=2$ gives the triple $(2,4,1)$ which is not. Prove that this random choice produces an arithmetic progression with probability at least $1/4$. (If you can prove this with a bigger probability than $1/4$, that's ok too. If you need to, you can assume that $M$ is sufficiently large for your proof to work.)

\smallskip
(b) Use your answer to (a) to argue that our test for 2-independence has constant probability of succeeding when used on the function $f_2$. (Your argument for this part can be heuristic rather than mathematically rigorous.)

\smallskip
(c) Prove that when used on a random function $r$, the test for 2-independence has a success probability that goes to zero in the limit as the range $N$ of the hash functions goes to infinity.
\end{problem}

\begin{solution}
% YOUR SOLUTION TO PROBLEM 4 GOES HERE
\end{solution}

\end{document}
