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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{am 13. 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{Tangob\"aume im Selbstversuch}{10 Punkte}

Sei $n = 15$. Bearbeiten Sie die Anfragefolge
$15,11,5,8,3$ mit einem Tangobaum.

Machen Sie dazu die einzelnen Schritte deutlich
(insbesondere die \texttt{cut} und \texttt{concat}
Operationen) und zeigen Sie die Atrribute
\texttt{refDepth}, \texttt{minDepth},
\texttt{maxDepth} und \texttt{isRoot} im Baum.
Zeigen Sie auch jeweils den aktuellen Zustand
des Referenzbaums.

\AUFGABE{Optimalit\"at von Tangob\"aumen}{10 Punkte}

Zeigen Sie, dass sich die Analyse der Tangob\"aume nicht
verbessern l\"asst. Konstruieren Sie dazu
f\"ur einen gegebenen Tangobaum beliebig lange Anfragefolgen
$\sigma$, so dass 
$\sigma$ insgesamt $\Omega(I(\sigma) \log\log n)$
Schritte ben\"otigt.

\AUFGABE{Die Wechselschranke}{10 Punkte}

Beweisen Sie:

\begin{enumerate}
  \item  Sei $\sigma$ eine zuf\"allige Permutation von
    $\{1, \dots, n\}$. Dann ist
    $\text{E}[I(\sigma)]= \Omega(n \log n)$.
  \item  
    Sei $\sigma = (a_1, \Delta_1), \dots, (a_m, \Delta_m)$ 
    eine Anfragefolge f\"ur das Teilsummenproblem, und
    sei $\sigma' = a_1, \dots, a_m$. 
    Wenn es einen dynamischen bin\"aren Suchbaum
    gibt, der $\sigma'$ mit Kosten $C$ bearbeitet,
    dann existiert eine Befehlsfolge f\"ur $\sigma$ mit L\"ange
    $O(C)$.
\end{enumerate}

\AUFGABE{Fast Optimale Bin\"are Suchb\"aume}{freiwillig, 10 Zusatzpunkte}

Seien $p_1, \dots, p_n$ mit $p_i > 0$ f\"ur $i=1, \dots, n$ und $\sum_{i=1}^n p_i = 1$
gegeben. Wir interpretieren $p_i$ als die Wahrscheinlichkeit,
dass auf Element $i$ zugegriffen wird. Nehmen Sie an, die $p_i$ liegen in einem Array
\texttt{P} vor, so dass $\texttt{P}[i] = p_i$ ist. Zeigen Sie,
dass man dann in $O(n)$ Zeit einen bin\"aren Suchbaum f\"ur $\{1,\dots,n\}$ mit
erwarteter Zugriffszeit $O(\sum_{i=1}^{n} p_i \log (1/p_i))$ konstruieren
kann.

\end{description}
\end{document}
