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

\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})}
\renewcommand{\labelenumii}{(\roman{enumii})}

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

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

\medskip\hrule
\smallskip
\noindent
Bearbeitungszeit: 90 Minuten.

\vskip 0.5cm

\begin{description}

\AUFGABE{Implementierungen eines ADT}{2+2+3+3 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 vier 
Datenstrukturen, beschreiben Sie jeweils kurz, wie man die 
Operationen \texttt{deleteMin} und \texttt{deleteMax} 
implementieren kann, und welche asymptotischen Laufzeiten man erh\"alt.
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; und
  \item unkomprimierter Trie.
\end{enumerate}

\AUFGABE{Huffman-Kodes}{1+6+3 Punkte}

 

\begin{enumerate}
\item 
  Wann hei\ss{}t ein Kode $C: \Sigma \rightarrow \{0,1\}^*$ 
  pr\"afixfrei? Wieso ist diese Definition n\"utzlich?
\item
  Sei $\Sigma = \{a,b,c,d,e,f\}$ mit H\"aufigkeiten
  $a :12$, $b:62$, $c:80$, $d:74$, $e:25$ und
  $f: 86$. Benutzen Sie den Algorithmus von Huffman, um einen
  Kode f\"ur $\Sigma$ zu den gegebenen H\"aufigkeiten zu bestimmen.
  Zeigen Sie die einzelnen Schritte. 
\item
  Bewerten Sie die folgende Aussage:
  ``Mit Huffmankodes kann man  
    eine gegebene Datei optimal komprimieren.''
\end{enumerate}

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

\begin{enumerate}
  \item  Was ist ein Entwurfsmuster? Was ist ein Algorithmus?
         Nennen Sie eine Gemeinsamkeit und einen Unterschied.
  \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 In der Vorlesung haben Sie mehrere Algorithmen gesehen, die
     dynamisches Programmieren verwenden. Warum findet man in diesen
     Algorithmen oft erst den \emph{Wert} einer optimalen L\"osung,
     bevor man eine optimale L\"osung selbst berechnet?
\end{enumerate}

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

\begin{enumerate}
  \item Beweisen Sie: Die erwartete Gr\"o\ss{}e einer Skipliste
      mit $n$ Schl\"usseln ist $O(n)$.
  \item
      Seien $L_1$ und $L_2$ zwei 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}
