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

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{am 1. 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}}



\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{Persistente Bin\"are Suchb\"aume}{10 Punkte}

F\"ugen Sie die Schl\"ussel A, L, P, D, R, E, I, F, O, M, N in dieser
Reihenfolge in einen anfangs leeren partiell persistenten AVL-Baum ein. Nehmen
Sie an, dass jeder Knoten maximal zwei Modifikationseinträge speichern kann.
L\"oschen Sie sodann die Schl\"ussel A, M, R. Zeichnen Sie den Baum nach jedem
Einf\"uge- und L\"oschvorgang (die Rückzeiger brauchen nicht gezeichnet zu
werden).

\AUFGABE{Amortisierte Analyse von partieller Persistenz}{10 Punkte}

In der Vorlesung haben wir ein Verfahren gesehen, um eine
Datenstruktur in der Pointer Machine in eine partiell persistente Datenstruktur
zu überführen, falls die maximale Anzahl der Zeiger auf einen Knoten konstant
ist. Zeigen Sie die folgenden Eigenschaften dieses Verfahrens:
\begin{enumerate}
  \item Das Anlegen der Modifikationseinträge (und ggf. Anlegen
    neuer Knoten, falls kein freies Modifikationsfeld mehr vorhanden ist),
    benötigt amortisiert nur $O(1)$ Zeit.
  \item Begründen Sie, warum aus der Analyse aus (a) folgt, dass das Anlegen der
    Modifikationseinträge amortisiert nur $O(1)$ zusätzlichen Speicherplatz benötigt.
  \item Sei $D$ eine Datenstruktur und $D'$ die partiell persistente
    Datenstruktur, die man durch Anwendung des Verfahrens aus der Vorlesung auf
    $D$ erhält. Bezüglich einer Folge von Operationen $o_1,o_2,\ldots,o_k$
    bezeichnen wir mit $D_i$ den Zustand von $D$ nachdem die Operationen
    $o_1,o_2,\ldots,o_i$ auf $D$ ausgeführt wurden ($D'_i$ analog). Folgern
    sie aus (a) und (b) die beiden Aussagen:
    \begin{enumerate}
      \item Sei $T_i$ die Zeit, die $D_{i-1}$ benötigt um die Operation $o_i$
        auszuführen. Dann benötigt $D'_{i-1}$ $O(T_i)$ amortisierte Zeit um $o_i$ auszuführen.
      \item Sei $s_i$ die Anzahl der Update-Schritte, die bei 
        Operation $o_i$ auf $D_{i-1}$ durchgef\"uhrt werden (Anlegen neuer Knoten,
	\"Andern von Zeigern, \"Andern von Feldern). Dann belegt $D'$ nach Ausführung der
        Operationen $o_1,\ldots,o_k$ insgesamt $O(\sum_{i=1}^k s_i)$
        Speicherzellen.
    \end{enumerate}
\end{enumerate}

\AUFGABE{Persistente Datenstrukturen und Punktlokalisierung}{10 Punkte}

Sei $G = (V, E)$ ein geometrischer Graph, d.h., die Knotenmenge
$V$ von $G$ ist eine endliche Punktmenge in der Ebene, und die
Kantenmenge $E$ von $G$ besteht aus Strecken, welche die
Punkte aus $V$ miteinander verbinden. Die Strecken aus $E$
schneiden sich h\"ochstens in ihren Endpunkten.
Im folgenden nehmen wir an, dass $G$ zusammenh\"angend ist.

\begin{enumerate}
  \item Geben Sie eine sinnvolle M\"oglichkeit an, wie man
  $G$ im Computer darstellen kann.
\end{enumerate}

Das \emph{Punktlokalisierungsproblem} besteht darin, eine
Datenstruktur f\"ur $G$ zu berechnen, welche die folgenden Anfragen beherrscht:
Gegeben ein Punkt $p \in \mathbb{R}^2$, finde die Facette von $G$,
welche $P$ enth\"alt.

\begin{enumerate}
 \setcounter{enumi}{1}
  \item Zeigen Sie, dass es gen\"ugt, die folgende Anfrage zu beantworten:
    Gegeben $p \in \mathbb{R}^2$, finde die Kante von $G$, welche direkt \"uber
    $p$ liegt (oder stelle fest, dass es keine solche Kante gibt).
  \item Zeigen Sie, wie man einen persistenten bin\"aren Suchbaum
    benutzen kann, um das Punktlokalisierungsproblem zu l\"osen.
    Ihre L\"osung sollte $O(n)$ Platz ben\"otigen und $O(\log n)$
    Anfragezeit erreichen.

  \emph{Hinweis}: Gehen Sie die Knoten von links nach rechts durch und erstellen
    Sie dabei einen geeigneten persistenten Suchbaum.
\end{enumerate}
\AUFGABE{Fractional Cascading}{30 Punkte}

In der Vorlesung haben Sie eine kurze Einf\"uhrung in die Technik des
Fractional Cascading erhalten. Besch\"aftigen Sie sich mit den beiden folgenden
Arbeiten:
\begin{itemize}
  \item
  Bernard Chazelle, Leonidas J.~Guibas: \emph{Fractional Cascading: I. A Data Structuring Technique}.
  Algorithmica 1(2): 133--162 (1986), und
  \item
    Bernard Chazelle, Leonidas J.~Guibas: \emph{Fractional Cascading: II. Applications}.
    Algorithmica 1(2): 163-191 (1986).
\end{itemize}
Erarbeiten Sie sich die noch fehlenden
theoretischen Grundlagen aus der ersten Arbeit. W\"ahlen Sie zwei
interessante Anwendungen aus der zweiten Arbeit, und pr\"asentieren Sie sie im Tutorium.
\end{description}
\end{document}
