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

\newcommand{\ZETTELNUMMER}{11}
\newcommand{\ABGABEDATUM}{bis zum 20. Januar 2017, 12 Uhr, in den
Briefkasten neben Raum 111}

\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

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Boris Klemz

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}
\AUFGABE {Quake Heaps: Details}{10 Punkte}

Beschreiben Sie die Details von Quake Heaps. Gehen
Sie dabei auf die folgenden Fragen ein:
Wie genau werden die Eintr\"age im Heap gespeichert?
Was wird in jedem Knoten des Turnierbaumes gespeichert?
Welche Schritte werden genau bei \texttt{insert}, \texttt{delete-min}
und \texttt{decrease-key} ausgef\"uhrt?
Wann und wie m\"ussen die Zeiger im Heap aktualisiert
werden? Wann und wie werden die Arrays \texttt{T[i]} und
\texttt{n[i]} aktualisiert?

\AUFGABE{Quake Heaps: Analyse}{10 Punkte}

Der Schritt in \texttt{delete-min}, der daf\"ur sorgt, dass es zu
jeder H\"ohe h\"ochstens einen Baum gibt, wird \emph{Konsolidierung}
genannt. In dieser Aufgabe sollen Sie sich \"uber verschiedene
Varianten der Konsolidierung Gedanken machen.

\begin{enumerate}
\item Nehmen Sie an, wir \"uberspringen in \texttt{delete-min} den 
  Konsolidierungsschritt.
  Wie \"andert sich dadurch die Laufzeitanalyse? 
\item Nehmen Sie an, dass wir am Ende von \texttt{delete-min}  
  eine weitere Konsolidierung durchf\"uhren,  falls ein Erdbeben
  stattgefunden hat. 
  Zeigen Sie, dass sich dadurch die amortisierten Laufzeiten 
  asymptotisch nicht \"andern.
\item (\emph{freiwillig, 5 Zusatzpunkte})
  Was passiert, wenn man die Konsolidierung statt in \texttt{delete-min}  
  am Ende von \texttt{insert} durchf\"uhrt?
\end{enumerate}


\AUFGABE{Potentialfunktionen}{10 Punkte}

In der Vorlesung haben wir Quake Heaps mit Hilfe der
Buchhaltermethode analysiert. Eine alternative Technik
verwendet so genannte \emph{Potentialfunktionen}. 
Wir betrachten eine Datenstruktur $D$. Sei $\mathcal{D}$
die Menge aller m\"oglichen Zust\"ande von $D$.
Eine Potentialfunktion $\Phi: \mathcal{D} \rightarrow \mathbb{N}_0$ 
ist eine Funktion, die jedem Zustand $D \in \mathcal{D}$ der Datenstruktur
eine nat\"urliche Zahl $\Phi(D)$ zuordnet. F\"ur den urspr\"unglichen
Zustand $D_0$ muss gelten: $\Phi(D_0) = 0$.

Wir definieren nun die \emph{amortisierten Kosten} einer Operation $X$ auf
  der Datenstruktur. Sei $D$ die Datenstruktur vor der Operation $X$ und $D'$ die
  Datenstruktur nach $X$. Seien $c_X$ die tats\"achlichen Kosten 
  von $X$. Dann sind die amortisierten Kosten von $X$, $\hat{c}_X$,
  definiert als $\hat{c}_X := c_X + \Phi(D') - \Phi(D)$.

\begin{enumerate}
\item 
  Geben Sie eine Interpretation der Potentialfunktion und erkl\"aren
  Sie die Intuition hinter der obigen Definition der amortisierten Kosten.
\item
  Sei $X_1$, $X_2,$, $\ldots$, $X_n$ eine Folge von Operationen,
  die auf der initialen Datenstruktur $D_0$ ausgef\"uhrt wird. 
  Zeigen Sie, dass 
  $\sum_i c_{X_i} \leq \sum_i \hat{c}_{X_i}$ ist. Interpretieren Sie das
  Ergebnis.
\item Betrachten Sie das Bin\"arz\"ahlwerk aus Aufgabe 2(a) auf dem 
  8. Aufgabenblatt. Sei $\Phi$ die Funktion, die einem Zustand des
  Bin\"arz\"ahlwerks die Anzahl der Einsen im aktuellen Z\"ahlerstand
  zuordnet. 
  
  Verwenden Sie $\Phi$, um zu zeigen, dass die amortisierten
  Kosten pro Z\"ahlvorgang konstant sind. Folgern Sie, dass das
  Bin\"arz\"ahlwerk mit Kosten $O(n)$ von $0$ bis $n$ z\"ahlen kann.
  Vergleichen Sie Ihren Beweis hier mit Ihrem Beweis vom 8. Aufgabenblatt.
\end{enumerate}

\AUFGABE{Quake Heaps: Implementierung}{10 Zusatzpunkte}

Implementieren Sie Quake Heaps in Java. F\"uhren Sie geeignete
Experimente durch und dokumentieren Sie diese.
Achten Sie auf angemessene
Kommentare im Quelltext. Geben Sie einen Ausdruck der wichtigsten
Kodefragmente ab und laden Sie au\ss{}erdem Ihren Quelltext im 
KVV hoch. 
\end{description}

\end{document}
