\documentclass[12pt]{article}
\usepackage{url}
\usepackage{fullpage}
\begin{document}
\thispagestyle{empty}
\begin{center}
{\Large \textsc{CS 270 Combinatorial Algorithms \& Data Structures} --- Spring 2023}
\bigskip
{\Large \textsc{Problem Set 4}}
\smallskip
Due: 11:59pm, Wednesday, March 8th
Solution maximum page limit: 3 pages
\bigskip
{\footnotesize See homework policy at \url{https://cs270.org/spring23/syllabus/#homework-policies}}
\end{center}
\paragraph{Problem 1:} (20 points) In {\em simple tabulation hashing}, we write a key $x\in[u]$ in base $u^{1/c}$ (assume $u^{1/c}$ is an integer and power of $2$) so that $x = \sum_{i=0}^{c-1} x_i \cdot u^{i/c}$. We call the $x_i$ ``characters''. We then allocate $c$ completely random lookup tables $H_0,\ldots,H_{c-1}$ each of size $[u^{1/c}]$. Then for each $y\in[u^{1/c}]$ we set $H_i(y)$ uniformly at random from $[m]$ (assume also $m$ is a power of $2$). Then to hash $x$, we define (where $\oplus$ denotes bitwise XOR)
$$h(x) = H_0(x_0)\oplus H_1(x_1)\oplus \cdots \oplus H_{c-1}(x_{c-1}) .$$
\begin{itemize}
\item[(a)] (5 points) Fix $c,m\ge 1$. Show that the family $\mathcal{H}$ of all such hash functions is $3$-wise independent.
\item[(b)] (5 points) Show that $\mathcal{H}$ is not $4$-wise independent.
\item[(c)] (10 points) Imagine using such an $\mathcal{H}$ to implement hashing with chaining. Show that if $m > n^{1.01}$ then with probability at least $2/3$, every linked list in the hash table has size $O(1)$. \textbf{Hint:} show that if a subset $T$ of the $n$ items is ``large'', then $\mathcal{H}$ behaves completely randomly on some ``somewhat large'' subset $T'$ of $T$.
\end{itemize}
\paragraph{Problem 2:} (20 points) In the {\it static} dictionary problem, $(x_1,v_1),\ldots,(x_n,v_n)$ are $n$ (key, value) pairs given up front, and we would like to create a data structure with low memory and fast preprocessing that supports querying keys in $O(1)$ worst-case time, guaranteed (not just in expectation!). A hash function $h:[U]\rightarrow[m]$ is {\it perfect} if $h(x_i) \neq h(x_j)$ for any $1\le i