\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}
\usepackage{geometry}

\usepackage{epsfig}%
\usepackage{graphics}%
\usepackage{enumerate}


\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'07)} \\[1ex]
{Prof.~Erik Demaine \quad\quad TA: Oren Weimann} \\[2ex]
\framebox{Problem 6} \quad {\em Due: Monday, Apr. 2}
\end{center}

Be sure to read the instructions on the assignments section of the
class web page.

\paragraph{\boldmath On Weak $d$-universal Hash Families.}

Recall that a set $\mathcal{H}$ of hash functions is a \emph{weak
$d$-universal family} if, for all $x,y \in U$ with $x \neq y$, $$\Pr_{h
\gets \mathcal{H}} \Big\{ h(x) = h(y) \Big\} = \frac{d}{m}.$$
%\begin{enumerate}
%\item In class we mentioned that $\mathcal{H}_{p,m}$ is
%weakly-universal (proof in Corman, Leiserson, Rivest, Stein,
%Introduction to algorithms 2$^{nd}$ edition). Show that
%$\mathcal{H}_{p,m}$ is not weakly 1-universal.
%
%\item
Let $U=\mathbb{Z}_2^\ell$ (the set of bit vectors of length~$\ell$).
For a given $k \times \ell$ binary matrix $M$, we
define a hash function $h_M: U \rightarrow \mathbb{Z}_2^k$ as
$h_M(x)=M \cdot x$, where additions and multiplications are done modulo~$2$.
Show that the family $\mathcal{H}=\{h_M \mid M$ is a
binary $k \times \ell$ matrix$\}$ is weakly $1$-universal.
%\end{enumerate}

\paragraph{\boldmath Deterministic y-fast tries.}
Suppose you have a dynamic perfect hash function $h$ such that:
\begin{itemize}
\item $h$ is constructible in deterministic linear time;
\item $h(x)$ can be evaluated in $O(1)$ worst case, deterministic time;
\item insertions and deletions take $O(\lg^5 u)$ worst case time;
\end{itemize}
Use $h$ to modify the y-fast trie data structure to support
insertion, deletion, predecessor, and successor in $O(\lg \lg u)$
amortized deterministic (rather than randomized) time.

\paragraph{\boldmath Range Existence Queries.}
Given a set $S$ of integers, the \emph{range existence query} $req(a,b)$
asks whether there is any element in $S \cap \{a,a+1,\ldots,b\}$. Suggest
an $O(n\lg u)$-space data structure that stores a static set $S$ of
$n$ integers from ${\mathcal U}=\{0,1,\ldots,u-1\}$ and
answers range existence queries in expected $O(1)$ time.

\emph{Hint:} Think why LCA queries in a perfect binary tree are easy.

\end{document}