\documentstyle[11pt]{article}

\begin{document}
\pagestyle{empty}
\parindent0pt

	We consider the problem of hashing records.  Each record
contains a key.  It may contain additional information. We have a
hash-table with $n$ slots numbered $1\ldots n$. When we get a new
record, a hash function is applied to its key to obtain a number $i$
between $1$ and $n$, and the record is then stored in the $i$th slot of
the hash-table. If multiple records get hashed to the same hash-table
location, then they are stored as a linked list.
	
	The hash functions are chosen to be
``random''. For the purposes of this question, we assume that a key
is hashed uniformly among the number $1$ to $n$ (i.e. with equal
probability).


	 In the two problems below we consider the complexity of
searching a hash-table. Assume the hash-table contains $n$ records.

\begin{enumerate}
\item {\em Expected max search time}
     \begin{itemize}
     \item Let $X_i$ be the number of records in the $i$'th location of 
     the hash-table. Prove that \[ Pr(X_i \geq k) \leq {n\choose k}
     \left(\frac{1}{n}     \right)^k \]
     \item Prove that ${n\choose k} \leq (\frac{ne}{k})^k$ and hence conclude 
     that \[ Pr(X_i \geq k) \leq (\frac{e}{k})^k \]
     \item If $k \geq (2e\ln n/\ln \ln n)$ then show that 
     \[ Pr(X_i \geq k) \leq n^{-2} \]
     \item Prove that the expected maximum search time for a record is not
     very large by showing that $E(max_i X_i) = O(\ln n/\ln \ln n)$. 
     \end{itemize}
\item {\em Expected average search time}
     \begin{itemize}
     \item Let $X_i$ be the number of records in the $i$'th location of 
     the hash-table. Prove that the expected average search time is
     \[E((\frac{1}{n})(\sum_iX_i(X_i + 1)/2)).\]
     \item Let $Y_j$ be the indicator variable which is $1$ if the $j$'th 
     record is hashed to the $i$'th location. Then $X_i = \sum_j Y_j$. Using
     the fact that the $Y_j$ are independent prove that $E(X_i^2) = 2 - 
     \frac{1}{n}$. 
     \item Show that the expected average search time is $1.5 - \frac{1}{2n}$.
     \end{itemize}
\end{enumerate}

\end{document}




