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

\newcommand{\ZETTELNUMMER}{1}
\newcommand{\ABGABEDATUM}{am 22. April 2014 vor der Vorlesung in die
Mitarbeiterschachteln}

\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 {Hashing mit Verkettung}{15 Punkte}

Angenommen, wir haben eine Hashtabelle mit $n$ Pl\"atzen, die
eine Menge $S \subseteq K$ der Gr\"o\ss{}e $n$ speichert. Konflikte
werden mit Hilfe von Verkettung gel\"ost. Wir nehmen an, dass
sich die Hashfunktion wie eine zuf\"allige Funktion verh\"alt.

F\"ur einen Platz $i$ in der Hashtabelle, bezeichne mit $Q_i$
die \emph{Anzahl} der Schl\"ussel, die auf $i$ gehasht werden.
Unser Ziel ist es, $\textbf{E}[\max_{i=0}^{n-1} Q_i]$ zu bestimmen,
also den Erwartungswert f\"ur die maximale Anzahl an Elementen, die
auf denselben Platz abgebildet werden.

\emph{Hinweis}: Bei jedem Aufgabenteil, mit Ausnahme von (d), gen\"ugt
eine Zeile als Antwort.

\begin{enumerate}
\item Begr\"unden Sie in einem Satz:
Es gilt f\"ur $i=0, \ldots, n-1$ und $r = 0, \ldots, n$,
\[
  \Pr[Q_i =  r] = \left(\frac{1}{n}\right)^r \left(1-\frac{1}{n}\right)^{n-r}
    \binom{n}{r}.
\]
\item Zeigen Sie,
\[
  \Pr\bigl[\max_{i=0}^{n-1} Q_i = r\bigr] \leq  n\Pr[Q_0 = r].
\]
\item Aus der Stirling-Formel folgt die Absch\"atzung
$\binom{n}{r} \leq (\frac{ne}{r})^r$. Benutzen Sie dies, um zu zeigen:
$\Pr[Q_0 = r] \leq e^r/r^r$.

\item Definiere $r_0 := c \log n / \log\log n$, f\"ur eine Konstante
$c > 1$. Zeigen Sie, dass man $c$ so w\"ahlen kann, dass
$\Pr[Q_0 = r] < 1/n^3$ ist, f\"ur alle $r \geq r_0$.

Folgern Sie daraus:
\[
  \Pr\bigl[\max_{i=0}^{n-1} Q_i \geq r_0\bigr] \leq  1/n.
\]
\item
Zeigen Sie
\[
  \textbf{E}\bigl[\max_{i=0}^{n-1} Q_i\bigr] \leq
r_0 \cdot  \Pr\bigl[\max_{i=0}^{n-1} Q_i < r_0\bigr] +
n \cdot \Pr\bigl[\max_{i=0}^{n-1} Q_i \geq r_0\bigr].
\]
Folgern Sie daraus:
$\textbf{E}[\max_{i=0}^{n-1} Q_i] = O(\log n/\log\log n)$.
\end{enumerate}

\AUFGABE{Amortisierte Analyse}{15 Punkte}

Eine Variante der amortisierten Analyse
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 Ein Binärzählwerk ist eine Datenstruktur, die einen Binärstring der Länge $n$
  speichert und nur eine einzige Funktion unterstützt, \texttt{increment}, die
  den gespeicherten Wert um genau eins erhöht. Die Kosten eines
  \texttt{increment}-Aufrufs sind dabei die Anzahl der Bits, die geändert werden
  müssen.

  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.
\end{enumerate}

\end{description}
\end{document}
