\documentclass[11pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{fullpage}

\setlength{\textwidth}{6.5in} \setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in} \setlength{\headsep}{0.0in}
%\setlength{\topsep}{0in}
\setlength{\textheight}{9in} \setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\newcommand{\floor}[1]{\ensuremath{\lfloor\, #1\,\rfloor}}


%\documentstyle[11pt]{article}
%\usepackage{fullpage}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\pagestyle{empty} \setlength{\textwidth}{6.5in}
%\setlength{\evensidemargin}{0.0in}
%\setlength{\oddsidemargin}{0.0in} \setlength{\topmargin}{-0.25in}
%\setlength{\textheight}{9.0in}
%\setlength{\baselineskip}{1.3\baselineskip}
%\setlength{\parindent}{0in}
%
%\newcommand\qed{\hspace*{\fill} {\large$\Box$}}
%\newcommand\set[1]{\left\{#1\right\}}
%\newcommand\ang[1]{\left\langle #1 \right\rangle}
%\newcommand\brac[1]{{\left[ {#1} \right]}}
%\newcommand\card[1]{\left| #1 \right|}
%\newcommand\inR{{~\in_{\rm R}~}}


\begin{document}



\title{Data Structures - Assignment no. 8, June 20, 2007}

\date{}

\maketitle


\def\lim{\mathop{\rm lim}\nolimits }
\def\true{ {\small\bf TRUE } }
\def\false{ {\small\bf FALSE } }

\vspace{-1.5cm}

 {\small {\bf Remarks:
\begin{itemize}
\item Write both your name and your ID number very clearly on the
top of the exercise. Write your exercises in pen, or in clearly
visible pencil. Please write \emph{very} clearly.

\item Recall that 80\% of the theoretical exercises must be
submitted. The exercises can and must be worked on and submitted
alone.

    \item  Give correctness and
        complexity proofs for every algorithm you write.
     \item For every question where you are required to write
     pseudo-code, also explain your solution in words.
\end{itemize} }}



\begin{enumerate}

\item Find the order of growth for the following recursively
    given functions, using the Master Method.
  \begin{enumerate}
  \item $T(n) = 4T(n/2)+n$
  \item $T(n) = 4T(n/2)+n^2$
  \item $T(n) = 4T(n/2)+n^3$
  \item Explain why $T(n) = 2T(n/2)+n log^2n $ cannot be solved using the Mater Method.
  \end{enumerate}

  \item Find the order of growth for the following recursively
    given functions. Explain your answer.

  \begin{enumerate}
  \item $T(n) = T(n-a) + T(a) + n $ where $ a \geq 1 $ is constant.
  \item $T(n) = T(cn) + T((1-c)n) + n $ where $ 0 < c < 1 $ is a constant.
  \item $T(n) = 2T(n/2)+n log^4n $ (Hint: The approach to solving this is
  similar to the approach to solving $T(n) = 2T(n/2)+n$).
  \end{enumerate}

%\item Prove that the solution for the recurrence
%  $T(n)=n^{2/3}T(n^{1/3})+n$ is $T(n)=\Theta(n \log \log n)$.

\item\footnote{borrowed from LSE exercise on hash tables}
Consider a hash table of size $m=1000$ and
the hash function
\begin{equation*}
h(k)=\floor{m \cdot (k \theta \; mod \; 1)}
\end{equation*}
for $\theta=(\sqrt{5}-1)/2$. Here, $x \mod 1$ is the fractional
part of the real number $x$, e.g.\ $15.1345 \mod 1 = 0.1345$.
Compute the locations to which the keys $61,62,63,64,65$ are
mapped.


%\item\footnotemark[1] Consider a hash table of size $m$ with open
%addressing and a probe sequence $a_0,a_1,a_2, \ldots$ in $\{0,1,
%\ldots, m-1\}$ defined by $a_i = (h(x)+i \cdot g(x)) \mod m$ for
%$i = 0,1,2, \ldots$, where $h(x)$ and $g(x)$ are uniform hash
%functions and where always $gcd(g(x),m) = 1$, that is, $g(x)$ has
%no nontrivial common divisor with $m$. What is the purpose of this
%last requirement?

%\item
%http://www.myoops.org/twocw/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JIntroduction-to-AlgorithmsFall2001/4AC6ECAF-F965-4E29-89F7-D227CA6FC46C/0/ps4.pdf

%\item
%http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/31E5676F-996F-4D89-B151-C70D502165C0/0/ps3.pdf

\item\footnote{borrowed from course at Bar-Ilan} A family 
$\mathcal{H}$ of functions from $U$ to $\{0,1,\ldots,m-1\}$ is called 
\emph{100-weakly universal} if for all $x,y \in U$ such that $x \neq y$ 
it holds that
\begin{equation*}
Pr_{h \leftarrow \mathcal{H}} [h(x)=h(y)]  \le \frac{100}{m} \ .
\end{equation*}

Let $U=\{0,1,\ldots,u-1\}$.
Define $f_a$ to be the function $f_a(x)=a \cdot x \mod m$. Show that 
$\mathcal{H}=\{f_a | 0<a<m\}$ is not a 100-weakly universal family. 

\item Show how to modify the Hash Table data structure, such that
all operations (find, insert and delete) take $O(\log n)$ time in
the worst-case. All operations should still take $O(1)$ time in
expectation. This question refers to the hash table data structure
that you learned in class, using universal hashing and chaining.
This does not refer to perfect hashing.

\item\footnote{taken from CLRS} A closed hash table of size $2n$ is used 
to store $n$ items. (Closed hash is sometimes also called ``open 
addressing'').

\begin{enumerate}

\item Assuming uniform hashing (i.e.\ each probe is done at a random 
location), show that for $i = 1, 2, \ldots, n$, the probability that the 
$i^{th}$ insertion requires strictly more than $k$ probes is at most 
$2^{-k}$.

\item Show that for $i = 1, 2, \ldots, n$, the probability that the 
$i^{th}$ insertion requires more than $2 \log n$ probes is at most $1/n^2$.

\item Let the random variable $X_i$ denote the number of probes required 
by the $i^{th}$ insertion. You have shown in part $(b)$ that $Pr(X_i >2 
\log n) \le 1/n^2$. Let the random variable $X = \max_{1 \le i \le n} 
X_i$ denote the maximum number of probes required by any of the $n$ 
insertions. Use the union-bound to show that $Pr(X > 2 \log n) \le 1/n$.

\item Use Markov's inequality this fact to show that the expected length 
of the longest probe sequence is $E[X] = O(\log n)$.

%Recall that for a random variable $Y$ which always takes 
%positive integer values, it holds that $E[Y]=\sum_{i > 0} Pr(Y \ge i)$ 
%(Remind youself why this is true).


\end{enumerate}

\end{enumerate}

\end{document}
