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

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{am 6. Mai 2014 vor der Vorlesung in die
Mitarbeiterschachtel}

\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]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung \hfill SoSe 2014

\smallskip
\noindent
\large
\textbf{Ausgewählte Themen der Algorithmik: Datenstrukturen}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Claudia Dieckmann, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE{Dynamische Optimalit\"at}{10 Punkte}

\begin{enumerate}
  \item Seien $T_1$ und $T_2$ zwei bin\"are Suchb\"aume mit
    Schl\"usselmenge  $\{1, \dots, n\}$. Zeigen Sie, dass sich
    $T_1$ mit $O(n)$ Rotationen in $T_2$ konvertieren l\"asst.
    Bestimmen Sie die Anzahl der Rotationen f\"ur Ihre Strategie im 
    schlimmsten Fall exakt.
    Versuchen Sie, so effizient wie m\"oglich zu sein.
  \item Sei $n = 5$. Betrachten Sie die Anfragefolge
    $\sigma = 2, 1,5, 1, 2, 4, 4, 2, 3, 5$.
    Bestimmen Sie $I(\sigma)$.
    Geben Sie eine m\"oglichst gute Bearbeitungsstrategie f\"ur $\sigma$ an.
    Berechnen Sie die Kosten f\"ur Ihren Algorithmus und vergleichen Sie
    sie mit $I(\sigma)$.
\end{enumerate}

\AUFGABE{Vereinigen und Trennen von AVL-B\"aumen}{20 Punkte}

Geben Sie die Details f\"ur die Operationen \texttt{join}
und \texttt{split} aus der Vorlesung.

\begin{itemize}
  \item \textbf{\texttt{join}}: Gegeben ein bin\"arer Suchbaum $T$,
    dessen linker und rechter Teilbaum jeweils 
    g\"ultige AVL-B\"aume sind, transformiere $T$ in einen g\"ultigten 
    AVL-Baum.
    Die Operation soll $T$ nur durch Rotationen ver\"andern 
    und $O(1 + |h_1 - h_2|)$
    Schritte ben\"otigen, wobei $h_1$ und $h_2$ die H\"ohen des
    linken und des rechten Teilbaums von $T$ sind.
  \item \textbf{\texttt{split}}:
    Gegeben ein AVL-Baum $T$ und ein Knoten $x \in T$,
    transformiere $T$ in einen bin\"aren Suchbaum mit  
    Wurzel $x$, so dass dass der linke und der rechte Teilbaum 
    jeweils g\"ultige AVL-B\"aume sind.
    Die Operation soll $T$ nur durch Rotationen ver\"andern 
    und $O(h)$
    Schritte ben\"otigen, wobei $h$ die H\"ohe von $T$ ist.
\end{itemize}

\end{description}
\end{document}
