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

\newcommand{\ZETTELNUMMER}{7}
\newcommand{\ABGABEDATUM}{am 08. Dezember~2017 bis 10 Uhr in die 
  jeweiligen Tutorenf\"acher}

\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}}
\newcommand{\N}{\mathbb{N}}

\renewcommand{\labelenumi}{(\alph{enumi})}


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

\smallskip
\noindent
\large
\textbf{Algorithmen, Datenstrukturen und Datenabstraktion}\hfill WS 17/18 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}
\AUFGABE{Hashing: Implementierung}{10 Punkte}

\begin{enumerate}
\item 
Lesen Sie die Dokumentation von \texttt{hashCode()} in
\texttt{java.lang.Object}. Welche zwei Bedingungen muss diese Funktion
erf\"ullen? Warum sollte man sie in eigenen
Klassen \"uberschreiben?
\item
Implementieren Sie Hashing mit Verkettung wie in der Vorlesung
beschrieben. 
Benutzen Sie dabei die Funktion
\texttt{hashCode()}.
F\"ur die verketteten Listen k\"onnen Sie die 
Java-Bibliothek verwenden.  Die Hashtabelle
soll dynamisch wachsen, sobald ein bestimmter Belegungsfaktor 
erreicht ist.


Experimentieren Sie mit ihrer Implementierung: 
Wie h\"angen die Zugriffszeiten vom Belegungsfaktor ab? 
Vergleichen Sie zwei verschiedene Hashfunktionen (diese 
k\"onnen f\"ur eine feste Gr\"o\ss{}e der Hashtabelle hart kodiert sein).  
\end{enumerate}

\AUFGABE{Hashing: Worst-case-Analyse}{10 Punkte}

Sei $A$ eine Hashtabelle der Gr\"o\ss{}e $N$, und $n \in \mathbb{N}$ 
beliebig. 
Zeigen Sie:
F\"ur jede Schl\"usselmenge $K$ mit $|K| \ge (n-1)N + 1$ und jede
Hashfunktion $h: K \to \{0, \dots,N-1\}$ existiert 
eine Menge $S \subseteq K$ mit
$|S|=n$, so dass alle Elemente von $S$ auf denselben Eintrag in
$A$ abgebildet werden. 
Was bedeutet das f\"ur die worst-case Laufzeit von Hashing mit
Verkettung?
Wie vertr\"agt sich das mit der Analyse aus der Vorlesung?

\AUFGABE{Offene Adressierung}{10 Punkte}

   Wir f\"ugen eine Menge $S$ von $n$ Eintr\"agen
  in eine Hashtabelle $T$ der L\"ange $m = 6n$ ein. 
  Die Kollisionsbehandlung
  erfolgt durch offene Adressierung mit linearem
  Sondieren. Wir nehmen an, dass die Hashfunktion $h$
  sich zuf\"allig verh\"alt. Die Indizes in $T$ 
  werden modulo $m$ gerechnet, d.h.,
  $T[-1] = T[m-1]$ und $T[m] = T[0]$. 

\begin{enumerate}
  \item Sei $k \in \N, k < m$. Ein \emph{Klumpen der L\"ange $k$} in $T$ 
    ist eine Folge $i, i + 1, \dots, i + k - 1$ von 
    aufeinanderfolgenden Indizes, so dass 
    $T[i], T[i+1], \dots, T[i+k-1]$ alle belegt sind, aber
    $T[i - 1]$ und $T[i + k]$ frei sind.

    Zeigen Sie: Die Wahrscheinlichkeit, dass $T$ nach
    dem Einf\"ugen von $S$ einen Klumpen der L\"ange
    $k$ enth\"alt, der bei $i$ beginnt, ist h\"ochstens
    \[
    p_{i,k} := \binom{n}{k}
           \left(\frac{k}{m}\right)^k\left(\frac{m-k}{m}\right)^{n-k}.
    \]

\emph{Hinweis}: Wenn ein Klumpen der L\"ange $k$ bei $i$ beginnt,
  so gibt es eine Teilmenge $S' \subseteq S$ von $k$ Eintr\"agen,
  die von $h$ nach $i, i+1, \dots, i+k-1$ abgebildet werden.
  Die anderen Hashwerte liegen au\ss{}erhalb dieser Menge.

 \item Zeigen Sie mit Hilfe von $m = 6n$ und der Absch\"atzung 
    $\binom{n}{k} \leq (\frac{ne}{k})^k$, 
    dass
    \[
    p_{i,k} \leq 2^{-k}
    \]
    ist. Hierbei ist $e \approx 2.71\dots$ die Eulersche Zahl.
\item Geben Sie eine m\"oglichst gute Absch\"atzung f\"ur die 
  Wahrscheinlichkeit, dass $T$ einen Klumpen der L\"ange $2\log n$  
  enth\"alt.
 
\item (\emph{freiwillig, 5 Zusatzpunkte}) Sei $x \notin S$ ein 
fester Schl\"ussel.  Argumentieren Sie, dass die
  erwartete Laufzeit zum Nachschlagen von $x$ in $T$ h\"ochstens 
  proportional ist zu
  \[
    1 + \sum_{k = 0}^{n} k 
    \Pr[\text{$h(x)$ liegt in einem Klumpen der L\"ange $k$]}.
    \tag{*}
  \]
  Zeigen Sie, dass sich (*) schreiben l\"asst als
  \[
    1 + \sum_{k = 0}^{n} k^2 
    \Pr[\text{ein Klumpen der L\"ange $k$ beginnt bei $h(x)$]}
    \tag{*}
  \]
  und folgern Sie, dass die erwartete Nachschlagezeit f\"ur $x$
  konstant ist.
\end{enumerate}

\AUFGABE{Kryptographische Hashfunktionen}{freiwillig, 10 Zusatzpunkte}

\begin{enumerate}
    \item Was ist eine kryptographische Hashfunktion? Nennen Sie drei  
        Beispiele.
     \item Welche kryptographischen Hashfunktionen sind in Java 
        implementiert? Wie kann man sie verwenden?
     \item Passen Sie Ihre Hashtabelle aus Aufgabe 1(b) so an,
       dass sie eine kryptographische Hashfunktion verwendet und
       f\"uhren Sie geeignete Tests durch.

       Nennen Sie einen Vorteil und einen Nachteil dieser Implementierung.
\end{enumerate}
\end{description}

\noindent
\emph{Hinweis}:
Bitte formatieren Sie Ihre Abgaben mit \LaTeX\xspace oder einem
vergleichbaren elektronischen Textverarbeitungssystem. Ansonsten droht
der Abzug von bis zu 10\% der erreichbaren Punkte.



\end{document}
