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

\newcommand{\ZETTELNUMMER}{8}
\newcommand{\ABGABEDATUM}{am 15. 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{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-1}$ besteht $L$ aus mindestens
    $j$ horizontalen Listen. 

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


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

\begin{enumerate}
\item 
Formulieren Sie den abstrakten Datentyp
\texttt{OrderedDictionary} 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 
Informieren Sie sich \"uber
die Spezifikation von \texttt{java.util.Iterator}.
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.

Achten Sie darauf, dass Sie die Spezifikation
von und \texttt{java.util.Iterator} aus der
API-Doku erf\"ullen. 
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
\emph{Observer Pattern}, und beschreiben Sie knapp, wie
es unser Problem l\"osen kann.

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

\newpage
\AUFGABE{Bin\"are Suchb\"aume}{10 Punkte}

\begin{enumerate}
  \item F\"ugen Sie die Schl\"ussel A, L, P, D, R, E, I, X, Y, Z in dieser
       Reihenfolge in einen anfangs leeren bin\"aren Suchbaum ein. 
       L\"oschen Sie sodann die Schl\"ussel
       Z, A, L. Zeichnen Sie
       den Baum nach jedem Einf\"uge- und L\"oschvorgang.
  \item Seien $T_1$ und $T_2$ zwei bin\"are Suchb\"aume, in
    denen jeweils die gleiche Menge $S$ von Eintr\"agen gespeichert
    ist, mit $|S|=n$. Zeigen Sie: Es gibt eine Folge von h\"ochstens
    $2n$ einfachen Rotationen, die $T_1$ nach $T_2$ \"uberf\"uhrt.
\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}

\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}
