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

\newcommand{\ZETTELNUMMER}{11}
\newcommand{\ABGABEDATUM}{am 11. Juli 2014 vor der Vorlesung}

\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})}
\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{Platzbedarf von Fractional Cascading}{10 Punkte}

Zeigen Sie: Beim Aufbau der erweiterten Kataloge
in der Fractional-Cascading-Datenstruktur ist der amortisierte Platzbedarf 
einer Einf\"ugeoperation $O(1)$. Dabei h\"angt die Konstante nicht
vom Maximalgrad $d$ ab.

Folgern Sie: Der Platzbedarf der erweiterten Kataloge ist $O(s)$.

\emph{Hinweis}: Benutzen Sie die Buchhaltermethode: Jeder neue 
  Katalogeintrag kostet einen Euro. F\"ur eine Einf\"ugeoperation
  veranschlagen wir 3 Euro. Ein Euro l\"asst sich in $d$ Cents
  umtauschen. Jede L\"ucke der Gr\"o\ss{}e  $k$ besitzt ein Sparschwein
  mit $2 \max \{0, k-3d\}$ Cents.

\AUFGABE{Dynamisierung von Datenstrukturen}{20 Punkte}

Wie in der Vorlesung angesprochen, l\"asst sich die 
Transformation einer statischen in eine halbdynamische
Datenstruktur so interpretieren, dass die aktuelle
Anzahl der Elemente als Bin\"arzahl dargestellt wird.
Unterschiedliche Zahlensysteme liefern unterschiedliche
Datenstruktur-Transformationen.

\begin{enumerate}
  \item Zeigen Sie: Jede Zahl $n \in \N$ l\"asst sich
    auf eindeutige Weise darstellen als
    $n = \binom{a}{2} + \binom{b}{1}$, f\"ur $a,b \in \N$ mit $a > b$.
  \item Benutzen Sie die Darstellung aus (a), um eine
    statische Datenstruktur mit Platzbedarf $S(n)$,
    Aufbauzeit $P(n)$ und Anfragezeit $Q(n)$ 
    in eine halbdynamische Datenstruktur mit
    Platzbedarf $O(S(n))$,
    amortisierter Einf\"ugezeit  $O(P(n) / \sqrt{n})$ und Anfragezeit $O(Q(n))$ zu transformieren.
  \item
    Zeigen Sie, wie meine eine statische Datenstruktur mit Platzbedarf $S(n)$,
    Aufbauzeit $P(n)$ und Anfragezeit $Q(n)$ 
    in eine halbdynamische Datenstruktur mit
    Platzbedarf $O(S(n))$,
    amortisierter Einf\"ugezeit  $O(P(n)/n)$ und Anfragezeit $O(\sqrt{n}Q(n))$ transformieren
    kann.
  \item
    Zeigen Sie, wie man bei der Transformation einer statischen in eine halbdynamsiche
    Datenstruktur einen Trade-Off zwischen der Anfragezeit und
    der amortisierten Einf\"ugezeit erreichen kann.

    \emph{Hinweis}:
     Sei $k \in \N$. Jede Zahl $n \in \N$ l\"asst sich
      auf eindeutige Weise darstellen als
      $n = \binom{a_k}{k} + \binom{a_{k-1}}{k-1}+ \dots + \binom{a_1}{1}$, f\"ur $a_1, \dots, a_k \in \N$
      mit $a_k > a_{k-1} > \dots > a_1$.
\end{enumerate}

\end{description}
\end{document}
