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

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{am 12. Januar~2018 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
\noindent
Dieser Zettel enth\"alt nur Zusatzaufgaben. Das AlP-3-Team
w\"unscht frohe Weihnachten und ein gutes neues Jahr.


\begin{description}
\AUFGABE{Rot-Schwarz B\"aume und $(2,4)$-B\"aume}{5 Punkte}

  Ein \emph{rot-schwarz Baum} ist ein bin\"arer Suchbaum, in dem 
  jeder Knoten eine Farbe hat: rot oder schwarz.
  Dabei muss folgendes gelten:
  (i) die Wurzel ist schwarz; (ii) die $\perp$-Knoten (d.h., die NULL-Knoten)
   sind schwarz; (iii) die Kinder eines roten Knoten sind
    schwarz; (iv) die \emph{schwarze Tiefe} aller $\perp$-Knoten
  ist gleich, d.h., f\"ur alle $\perp$-Knoten ist die Anzahl der
  schwarzen Knoten auf dem Pfad von der Wurzel zum jeweiligen Knoten gleich.

      Zeigen Sie: Rot-schwarz B\"aume und $(2,4)$-B\"aume sind
      \"aquivalent. Genauer: es gibt eine lokale Transformation,
      welche Gruppen von Knoten im rot-schwarz Baum in Knoten im
      $(2,4)$-Baum \"uberf\"uhrt, und umgekehrt. Geben Sie eine solche
      Transformation an, und begr\"unden Sie, dass Ihre Transformation
      die Bedingungen an rot-schwarz B\"aume und an
      $(2,4)$-B\"aume erf\"ullt.

\AUFGABE{Huffman-Implementierung --- Entwurf}{10 Punkte}

Implementieren Sie den Huffman-Kodierungsalgorithmus.
Genauer: Schreiben Sie zwei Java-Programme \texttt{HuffmanEncode}
und \texttt{HuffmanDecode}. Bei Eingabe des Befehls
\texttt{java HuffmanEncode foo} soll die Datei \texttt{foo}
eingelesen und mit dem Huff\-man-Algorithmus (auf Byteebene)
komprimiert werden. Das Ergebnis (zusammen mit der Kodetabelle)
soll in eine Datei \texttt{foo.hc} geschrieben werden.
Beim Aufruf von \texttt{java HuffmanDecode foo.hc} soll
die komprimierte Datei \texttt{foo.hc}  gelesen 
und die entkomprimierte Version in die Datei \texttt{foo.uc}
geschrieben werden.

\"Uberlegen Sie sich einen geeigneten Entwurf f\"ur das Programm.
Welche Teilprobleme m\"ussen gel\"ost werden? Welche abstrakten Datentypen
werden ben\"otigt? Wie lassen sich die Teilprobleme auf Klassen aufteilen?
Wie sollen die Klassen miteinander interagieren? Wie soll der Programmablauf
stattfinden? Beschreiben Sie knapp Ihren Entwurf
und visualisieren Sie ihn mit geeigneten Diagrammen.

\AUFGABE{Huffman-Implementierung --- Umsetzung}{15 Punkte}

Setzen Sie Ihren Entwurf aus der letzten Aufgabe in die Tat um und
testen Sie Ihr Programm an geeigneten Beispielen.

\newpage

\AUFGABE{Erwartete Pfadl\"ange in einem bin\"aren Suchbaum}{10 Punkte}

Seien $n$ verschiedene Schl\"ussel
aus einem total geordneten Universum gegeben. Der
\emph{zuf\"allig aufgebaute bin\"are Suchbaum} auf diesen $n$ Schl\"usseln
ist der bin\"are Suchbaum, welcher entsteht, wenn man die $n$ Schl\"ussel
in zuf\"alliger Reihenfolge in einen anfangs leeren bin\"aren Suchbaum
einf\"ugt. Dabei ist jede der $n!$ m\"oglichen Einf\"ugereihenfolgen gleich
wahrscheinlich.

\begin{enumerate}
        \item Zeigen Sie: die Wahrscheinlichkeitsverteilung, 
                wenn man einen bin\"aren Suchbaum  aus $n$
                Schl\"usseln zuf\"allig aufgebaut, unterscheidet sich
		von der Verteilung,
                wenn man gleichverteilt einen
                bin\"aren Suchbaum auf $n$ Elementen ausw\"ahlt.

                \emph{Hinweis}: Betrachten Sie den Fall $n=3$.
\end{enumerate}

Bezeichne zu einem Knoten $x$ aus $T$ die Tiefe von $x$ mit $d(x, T)$.
Dann ist die \emph{innere Pfadl\"ange von $T,$} $P(T)$, definiert als
\[
P(T) = \sum_{x \in T} d(x, T).
\]
Wir wollen nun zeigen, dass $\textbf{E}[P(T)] = O(n \log n)$ ist.

\begin{enumerate}
\setcounter{enumi}{1}
\item Seien $T_L$ und $T_R$ der linke und der rechte Teilbaum von $T$. Zeigen
Sie: 
\[
P(T) = P(T_L) + P(T_R) + |T|-1.
\]

\item Sei $P(n)$ die erwartete innere Pfadl\"ange eines zuf\"allig
aufgebauten bin\"aren Suchbaums mit $n$ Elementen. Folgern Sie aus der
vorherigen Aufgabe, dass 
\[
P(n) = \frac{1}{n}\sum_{k=0}^{n-1}\left(P(k) + P(n-k-1) + n -1 \right).
\]

\item L\"osen Sie die Rekursionsgleichung aus (c) mit
einer Methode Ihrer Wahl (machen Sie geeignete Annahmen \"uber den
Rekursionsanker).

\item Folgern Sie, dass die durchschnittliche Tiefe eines Knoten
in einem zuf\"allig aufgebauten bin\"aren Suchbaum $O(\log n)$ ist.

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