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

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{am 28. November 2013 vor der Vorlesung 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}}



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


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

\smallskip
\noindent
\large
\textbf{Algorithmen und Programmierung III} \\[0.5ex]
\normalsize
Wolfgang Mulzer \hfill WiSe 2013/14

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Hashing im Selbstversuch}{10 Punkte}

\begin{enumerate}
  \item  
    F\"ugen Sie nacheinander die Schl\"ussel 5, 28, 19, 15, 20, 33, 12, 17, 10
    in eine Hashtabelle der Gr\"o\ss{}e 9 ein. Die Hashfunktion sei
    $h(k) = k \bmod 9$. Die Konflikte werden mit Verkettung gel\"ost.
  \item 
    F\"ugen Sie nacheinander die Schl\"ussel 10, 22, 31, 4, 15, 28, 17, 88, 59
    in eine Hashtabelle der Gr\"o\ss{}e 11 ein. Die Hashfunktion sei
    $h(k) = k \bmod 11$. Die Konflikte werden durch
    offene Adressierung mit linearem Sondieren gel\"ost.
  \item 
    F\"ugen Sie nacheinander die Schl\"ussel 10, 22, 31, 4, 15, 29, 17, 88, 59
    in eine Hashtabelle der Gr\"o\ss{}e 11 ein. Die Konflikte werden
    durch Kuckuck mit $h_1(k) = k \bmod 11$ und
    $h_2(k) = (k \bmod 13) \bmod 11$.
\end{enumerate}

Illustrieren Sie jeweils die einzelnen Schritte.

\emph{Hinweis}: Pseudocode f\"ur die Hashoperation findet
     sich auf der Website.

\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?
\end{description}
\end{document}
