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


\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]
Probeklausur 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
Bearbeitungszeit: mindestens 90 Minuten

\vskip 0.5cm

\begin{description}

\AUFGABE{Implementierungen eines ADT}{3+3+4 Punkte}

Betrachten Sie die folgende Spezifikation eines abstrakten Datentypen:
Sei $\mathcal{U}$ ein total geordnetes Universum. Es sollen Teilmengen
$S \subseteq U$ gespeichert werden, so dass folgende Operationen
m\"oglich sind:
\begin{itemize}
  \item \texttt{insert}(x): Voraussetzung: keine. Wirkung:
                  $S \mapsto S \cup \{x\}$.
  \item \texttt{deleteMin}(): Voraussetzung: $S$ ist nicht leer. Wirkung:
                  $S \mapsto S \setminus \{\min S\}$.
  \item \texttt{deleteMax}(): Voraussetzung: $S$ ist nicht leer. Wirkung:
                  $S \mapsto S \setminus \{\max S\}$.
\end{itemize}
Sie d\"urfen annehmen, dass sich zwei Elemente aus $\mathcal{U}$ in 
konstanter Zeit vergleichen lassen. F\"ur jede der folgenden drei
Datenstrukturen, beschreiben Sie jeweils kurz, wie man die 
Operationen \texttt{deleteMin} und \texttt{deleteMax} 
m\"oglichst effizient implementieren kann, und geben Sie m\"oglichst
gute asymptotische obere Schranken f\"ur die Laufzeit.
Erkl\"aren Sie gegebenenfalls, welche zus\"atzlichen Annahmen n\"otig sind.

\begin{enumerate}
  \item Sortierte doppelt verkettete Liste mit Zeigern auf das erste und 
        das letzte Element;
  \item AVL-Baum;
  \item bin\"arer Min-Heap. 
\end{enumerate}

\AUFGABE{Hashing}{2+4+4 Punkte}

\begin{enumerate}
\item 
Hashing mit Verkettung bietet $O(1)$ \emph{erwartete}
Laufzeit  pro Operation. Was bedeutet das?
Was kann man \"uber die \emph{worst-case} Laufzeit sagen?
\item
Sei $T$ eine Hashtabelle mit Verkettung, die $m$ Pl\"atze hat
und eine Menge $S$ von $2m$ Eintr\"agen speichert. Zeigen Sie: Unter der 
Annahme, dass die Hashfunktion $h$ zuf\"allig gew\"ahlt ist, ist die 
erwartete Zeit zum Finden eines festen Elementes $x$ in der 
Hashtabelle $O(1)$. Nehmen Sie an, dass $h(x)$ in $O(1)$ Zeit
berechnet werden kann.
\item
Sei $T$ eine Hashtabelle mit $n$ Pl\"atzen,
in der wir eine Menge $S$ mit $n$ Eintr\"agen speichern.
Sei $h$ eine Hashfunktion. 

Was versteht man unter
einer \emph{Kollision} unter $h$?
Berechnen Sie die erwartete Anzahl \emph{aller} Kollisionen
in $T$
unter der Annahme, dass sich $h$ wie eine
zuf\"allige Funktion verh\"alt.

\emph{Hinweis}: Betrachten Sie alle Paare von Eintr\"agen aus
$S$ und verwenden Sie die Linearit\"at des Erwartungswerts.
\end{enumerate}

\newpage
\AUFGABE{Vermischtes}{3+2+2+3 Punkte}

\begin{enumerate}
  \item  Was versteht man unter einer kryptographischen Hashfunktion?
     Nennen Sie zwei Eigenschaften und eine Anwendung.
  \item Was ist der Unterschied zwischen dem dynamischen und dem
       statischen Datentypen einer Variable? Geben Sie ein kurzes
       Beispielfragment in Java.
%  \item Beschreiben Sie ein kurz ein Problem, das sich mit dem 
%     \emph{factory method} Entwurfsmuster l\"osen l\"asst.
  \item  Unter welchen Umst\"anden ist eine Datenstruktur, die
     $O(\log n)$ \emph{amortisierte} Laufzeit f\"ur eine Operation 
     ben\"otigt,
     einer Datenstruktur vorzuziehen, die $O(\log n)$ \emph{worst-case}
     Laufzeit f\"ur die gleiche Operation ben\"otigt?
  \item  Was versteht man unter einem \emph{abstrakten Datentypen}?
    Nennen Sie zwei Beispiele aus der Vorlesung und erkl\"aren
    Sie das Prinzip, auf dem das Konzept des abstrakten Datentypen
    basiert.
\end{enumerate}

\AUFGABE{Skiplisten}{4+3+3 Punkte}

\begin{enumerate}
  \item Beweisen Sie: Die erwartete Gr\"o\ss{}e einer zuf\"allig
  aufgebauten Skipliste mit $n$ Eintr\"agen ist $O(n)$.
  \item
      Seien $L_1$ und $L_2$ zwei zuf\"allig aufgebaute Skiplisten, 
      welche jeweils die 
      Schl\"usselmenge $K_1$ und $K_2$ speichern. Beschreiben Sie
      einen effizienten Algorithmus, der aus $L_1$ und $L_2$ eine Skipliste 
      f\"ur die Menge
      $K_1 \cup K_2$ konstruiert. Analysieren Sie die erwartete Laufzeit
      Ihres Algorithmus. (Sie k\"onnen dabei die Aussage von (a) verwenden.)
  \item Nehmen Sie nun bei (b) zus\"atzlich an, dass f\"ur alle 
  $k_1 \in K_1$,
      $k_2 \in K_2$ gilt: $k_1 < k_2$. Das hei\ss{}t, jeder Schl\"ussel in
      $L_1$ ist kleiner als alle Schl\"ussel in $K_2$. Geben Sie nun 
      einen Algorithmus an,
      der $L_1$ und $L_2$ in erwarteter Zeit 
      $O(\max\{\log |K_1|, \log |K_2|\})$ vereinigt, und beweisen Sie 
      die Laufzeitgarantie.

      \emph{Hinweis:} F\"ur alle $x \in (0,1)$ gilt:
        $\sum_{i=1}^{\infty} ix^i = x/(1-x)^2$.
\end{enumerate}
\end{description}
\end{document}
