\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage[utf8x]{inputenc}

\newcommand{\ZETTELNUMMER}{9}
\newcommand{\ABGABEDATUM}{am 17. Juni 2014 vor der Vorlesung} 

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung \hfill SoSe 2014

\smallskip
\noindent
\large
\textbf{Ausgewählte Themen der Algorithmik: Datenstrukturen}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Claudia Dieckmann, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Perfektes Hashing}{10 Punkte}

Sei $U$ eine Menge von $u$ Schl\"usseln und $T$ eine Hashtabelle
mit $m$ Pl\"atzen.
Eine Familie $\mathcal{H}$ von Hashfunktionen $h : U \rightarrow \{0, \dots, m-1\}$
hei\ss{}t \emph{universell}, falls f\"ur alle $s \neq t \in U$  gilt
\[
  \Pr_{h \in \mathcal{H}}[h(s) = h(t)] \leq 1/m.
\]
Beweisen Sie:
\begin{enumerate}
  \item 
    Sei $S \subset U$ eine Menge von $n$ Schl\"usseln, die in einer
    Hashtabelle mit $n$ Pl\"atzen gespeichert sind. Nehmen Sie an,
    die Hashfunktion $h$  wird zuf\"allig gleichverteilt aus einer
    universellen Hashfamilie $\mathcal{H}$ gew\"ahlt. Sei $n_i$ die Anzahl der Schl\"ussel
    in $S$, die auf den Platz $i$ gehasht werden. Dann ist die erwartete Zeit f\"ur eine
    \texttt{lookup}-Operation $O(1)$ und  es gilt
    \[
      \text{E}_{h \in \mathcal{H}} \Bigl[\sum_{i=0}^{n-1} n_i^2\Bigr] \leq 2n.
    \]
  \item
    Sei $S \subset U$ eine Menge von $n$ Schl\"usseln, die in einer
    Hashtabelle mit $n^2$ Pl\"atzen gespeichert sind. Nehmen Sie an,
    die Hashfunktion $h$  wird zuf\"allig gleichverteilt aus einer
    universellen Hashfamilie $\mathcal{H}$ gew\"ahlt. Eine \emph{Kollision}
    von $S$ unter $h$ ist ein ungeordnetes Paar $s \neq t \in S$ von 
    Schl\"usseln mit $h(s) = h(t)$.
    Es gilt:
    \[
      \text{E}_{h \in \mathcal{H}} [\text{Anzahl Kollisionen von $S$ unter $h$}] \leq 1/2.
    \]
\end{enumerate}

\AUFGABE{Tabulation Hashing}{5 Punkte}

Sei $k \in \mathbb{N}$. Eine Familie $\mathcal{H}$ von Hashfunktionen 
$h: U \rightarrow \{0, \dots, m\}$ hei\ss{}t
\emph{$k$-unabh\"angig}, falls f\"ur alle $k$-Tupel
$(s_1, \dots, s_k) \in U^k$ von paarweise verschiedenen
Schl\"usseln und f\"ur alle $k$-Tupel 
$(x_1, \dots, x_k) \in \{0, \dots, m-1\}^k$ von Pl\"atzen gilt:
\[
  \Pr_{h \in \mathcal{H}}\Bigl[\bigwedge_{i=1}^k h(s_i) = x_i\Bigr]
   = \prod_{i=1}^{k} \Pr_{h \in \mathcal{H}}[h(s_i) = x_i].
\]
Beweisen Sie, dass Tabulation Hashing eine Familie von Funktionen
liefert, die 3-unabh\"angig ist, aber nicht 
4-unabh\"angig.

\AUFGABE{Lineares Sondieren}{15 Punkte}

In dieser Aufgabe sollen Sie Hashing mit linearem Sondieren
analysieren unter der Annahme, dass die Hashfunktion sich
wie eine zuf\"allige Funktion verh\"alt.
\begin{enumerate}
  \item Rufen Sie sich ins Ged\"achtnis, wie Hashing mit linearem
    Sondieren funktioniert. Geben Sie Pseudocode f\"ur die Operationen
    \texttt{insert} und \texttt{lookup}.
\end{enumerate}
 Nehmen Sie nun an, dass wir eine Menge $S$ von $n$
 Schl\"usseln in einer Hashtabelle $T$ mit $m = 2n$
 Pl\"atzen hashen, wobei lineares Sondieren zum Einsatz kommt.
 Wir sagen, die Hashtabelle enth\"alt einen
 \emph{Lauf der L\"ange $k$ an der Stelle $i$},
 wenn $T[i-1] = T[i+k] = \perp$ und $T[i], T[i+1],\dots, T[i+k-1] \neq \perp$
 sind.
 \begin{enumerate}
    \item
      Zeigen Sie: Die Wahrscheinlichkeit, dass ein Lauf der L\"ange $k$ an
      der Stelle $i$ beginnt,
      ist h\"ochstens
      \[
        p_k = \binom{n}{k}\Bigl(\frac{k}{m}\Bigr)^k\Bigl(\frac{m-k}{m}\Bigr)^{n-k}
      \]
    \item Zeigen Sie: es gibt eine Konstante $c \in (0,1)$, so dass 
      $p_k = O(c^k)$ ist.

    \emph{Hinweis:} Benutzen Sie die Stirling-Formel
      $n! = (n/e)^n\sqrt{2\pi n}(1 + o(1))$, um die Fakult\"aten im 
      Binomialkoeffizienten abzusch\"atzen.
    \item Sei $s \in U \setminus S$ ein Schl\"ussel. Zeigen Sie: 
      Die erwartete Laufzeit f\"ur \texttt{lookup}$(s)$  ist $O(1)$.

      \emph{Hinweis}: Falls $h(s)$ in einem Lauf der L\"ange $k$ liegt, ist die
        Anfragezeit f\"ur $s$ h\"ochstens $k$. Ihre Herleitung sollte
	ergeben, dass die erwartete Suchzeit h\"ochstens
	$\sum_{k=0}^{n} k^2 p_k$ ist.
 \end{enumerate}
\end{description}
\end{document}
