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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{am 20. 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{Van-Emde-Boas-B\"aume: Kleinigkeiten}{10 Punkte}

\begin{enumerate}
  \item
  Geben Sie Pseudocode wie in der Vorlesung f\"ur die \texttt{delete}-Operation in
  van-Emde-Boas-B\"aumen. Beschreiben Sie Ihren Algorithmus auch in Worten und analysieren Sie die Laufzeit.
  \item
    L\"osen Sie die folgenden Rekursionsgleichungen und diskutieren
    Sie ihre Relevanz f\"ur van-Emde-Boas-B\"aume.
    Machen Sie geeignete Annahmen \"uber den Rekursionsanker.
    \begin{enumerate}
      \item $T(N) = T(\sqrt{N}) + O(1)$;
      \item $T(N) = 2 T(\sqrt{N}) + O(1)$; und
      \item $S(N) = (\sqrt{N} + 1)S(\sqrt{N}) + O(\sqrt{N})$.
    \end{enumerate}
\end{enumerate}

\AUFGABE{Van-Emde-Boas-B\"aume: Initialisierung}{10 Punkte}

\begin{enumerate}
  \item
    Sei \texttt{T} ein Feld der L\"ange $N$.
    Zu Beginn kann \texttt{T} beliebige Daten enthalten.

    Wir nehmen an, dass $N$ riesig ist und wir keine 
    Zeit haben, um \texttt{T} zu initialisieren. Beschreiben
    Sie, wie wir \texttt{T} dennoch verwenden
    k\"onnen, um sinnvoll Daten zu speichern. Ihre Methode
    soll jeden Zugriff auf \texttt{T} in $O(1)$ Zeit 
    unterst\"utzen.


    \emph{Hinweis}: Verwenden Sie ein zus\"atzliches Feld, um
      die g\"ultigen Eintr\"age in \texttt{T} zu speichern.
  \item
    Bei van-Emde-Boas B\"aumen scheint es auf den ersten
    Blick notwendig zu sein, $O(N)$ Zeit in die Initialisierung
    des Baumes zu investieren. Beschreiben Sie, wie es besser geht.

    \emph{Hinweis}: Verwenden Sie (a). 
\end{enumerate}

\AUFGABE{Union-Split-Find}{10 Punkte}
Entwerfen und analysieren Sie eine Word-RAM Datenstruktur, die eine
Menge von disjunkten Intervallen der Form $[a,b)$ speichert, mit
$a,b \in \mathcal{U}$.
Ihre Datenstruktur soll die folgenden Operationen in $O(\log\log N)$
Zeit unterst\"utzen:
\begin{itemize}
\item \texttt{make}$(a, b)$: Erzeuge das Intervall $[a, b)$ (Sie d\"urfen annehmen, dass $[a,b)$ 
keines der vorhandenen Intervalle schneidet).
\item \texttt{union}$(a, b, c)$: Vereinige die benachbarten Intervalle $[a, b)$ und $[b, c)$ zu $[a, c)$
 (Sie d\"urfen annehmen, dass $[a,b)$ und $[b,c)$ vorhanden sind).
\item \texttt{split}$(a, b, k)$: F\"ur $k \in [a, b)$, teile das Intervall $[a, b)$ in $[a, k)$ und $[k, b)$.
\item \texttt{find}$(k)$: Finde das  Intervall $[a, b)$ das $k$ enth\"alt, falls vorhanden.
\end{itemize}



\end{description}
\end{document}
