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

\newcommand{\ZETTELNUMMER}{7}
\newcommand{\ABGABEDATUM}{am 5. Dezember 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{Offene Adressierung}{10 Punkte}

  Sei $T$ eine leere Hashtabelle der L\"ange
  $m$. Wir f\"ugen nacheinander $n \leq m/2$ Eintr\"age
  in $T$ ein. Die Kollisionsbehandlung
  erfolgt durch offene Adressierung mit linearem
  Sondieren. Wir nehmen an, dass die Hashfunktion
  sich zuf\"allig verh\"alt.

\begin{enumerate}
  \item Zeigen Sie: f\"ur jede Einf\"ugeoperation ist
    die Wahrscheinlichkeit, dass mindestens
    $k$ Positionen in $T$ inspiziert werden,
    h\"ochstens $2^{1-k}$. 

\emph{Achtung}: Sie d\"urfen annehmen, dass jeder
  Eintrag der Tabelle unabh\"angig mit Wahrscheinlichkeit
  $1/2$ besetzt ist. Das stimmt zwar nicht, aber andernfalls
  ist die Analyse schwierig
 \item Folgern Sie: f\"ur jede Einf\"ugeoperation ist
    die Wahrscheinlichkeit, dass mindestens
    $2\log n$ Positionen in $T$ inspiziert werden,
    h\"ochstens $1/n^2$. 
\item Mit Wahrscheinlichkeit mindestens $1-1/n$
  ben\"otigen alle Einf\"ugeoperationen jeweils h\"ochstens
  $O(\log n)$ Schritte.

   \emph{Hinweis}: F\"ur Ereignisse $A_1, \dots, A_\ell$
   gilt: $\Pr[A_1 \vee \dots \vee A_\ell]
   \leq \sum_{i=1}^{\ell} \Pr[A_i]$.
\end{enumerate}

\AUFGABE{Analyse von Skiplisten}{10 Punkte}

Sei $L$ eine Skipliste mit $n$ Eintr\"agen.
Zeigen Sie:
\begin{enumerate}
  \item Die erwartete Anzahl von Knoten in $L$ 
     ist $O(n)$.
  \item Mit Wahrscheinlichkeit h\"ochstens
    $n/2^j$ besteht $L$ aus mindestens
    $j$ Listen. 
   \emph{Hinweis}: Beachten Sie den Hinweis von 1c.
\end{enumerate}

\AUFGABE{Implementierung des geordneten W\"orterbuchs}{10 Punkte}

\begin{enumerate}
\item 
Formulieren Sie den abstrakten Datentyp
\emph{geordnetes W\"orterbuch} aus der Vorlesung 
als Java-Schnittstelle. Achten Sie dabei auf
eine geeignete Spezifikation der Methoden
in ihren Kommentaren. Implementieren Sie
die Schnittstelle mit einer Skipliste. 

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

\item 
F\"ugen Sie zwei Methoden
\texttt{reverseIterator()} und \texttt{iterator()}
hinzu,
welche jeweils ein \texttt{Iterator}-Objekt 
erzeugen. Der Iterator von
\texttt{iterator()} soll die
Eintr\"age in sortierter Reihenfolge durchlaufen,
\texttt{reverseIterator()} soll
die Eintr\"age in umgekehrter Reihenfolge liefern.

Informieren Sie sich \"uber
die Spezifikation von \texttt{java.util.Iterator},
und setzen Sie sie um.
Sie m\"ussen nicht die \texttt{remove()}-Operation
unterst\"utzen.
\item
(\emph{freiwillig} 5 Zusatzpunkte)

Was passiert, wenn die Skipliste ver\"andert wird, w\"ahrend ein
\texttt{Iterator}-Objekt aktiv ist? Beschreiben Sie ein 
m\"ogliches Problem.

Ein L\"osung bieten \emph{fail-fast} Iteratoren: sobald die
Skipliste via \texttt{put} oder \texttt{remove} ver\"andert wird,
werden \emph{alle} aktiven \texttt{Iterator}-Objekte ung\"ultig.
Sp\"atere Methodenaufrufe liefern dann eine
\texttt{ConcurrentModificationException}. Iteratoren,
welche nach der Modifikation erzeugt wurden, 
sollen aber weiterhin funktionieren. Wie kann man dieses
Verhalten umsetzen? Informieren Sie sich \"uber das
Entwurfsmuster \emph{Observer}, und beschreiben Sie knapp, wie
es unser Problem l\"osen kann.

Bei dieser Teilaufgabe m\"ussen Sie nichts implementieren.
\end{enumerate}

\AUFGABE{Cuckoo Hashing (freiwillig)}{10 Zusatzpunkte}

Sehen Sie sich die Bachelorarbeit zum Thema
Cuckoo-Hashing an, und beantworten Sie folgende Fragen.
\begin{enumerate}
  \item Was ist der Kuckucksgraph?
  \item Wie ist der Zusammenhang zwischen dem Kuckucksgraphen und dem Erfolg der Einf\"ugeprozedur?
    Warum (kurze Begr\"undung)?
  \item Was ist eine Kodierung?
  \item Wie benutzt man Kodierungen, um zu zeigen, dass ein Ereignis geringe
    Wahrscheinlichkeit haben muss?
  \item Welche Variante von Cuckoo-Hashing ist in der Praxis am effizientesten?
\end{enumerate}

\end{description}
\end{document}
