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

\newcommand{\ZETTELNUMMER}{7}
\newcommand{\ABGABEDATUM}{bis zum 9. Dezember 2016, 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{Das Offline-Minimum-Problem} {10 Punkte}

Beim Offline-Minimum-Problem sollen 
wir eine dynamische Menge 
$T \subseteq \{1, \dots, n\}$
verwalten, welche durch die Operationen
\textbf{insert} und \textbf{extract-min} 
ver\"andert wird, beginnend mit $T = \emptyset$.
Wir erhalten eine Folge $S$ von $n$ \textbf{insert}
und $m$ \textbf{extract-min} Operationen, bei der
jedes Element in $\{1, \dots, n\}$ 
\emph{genau einmal} eingef\"ugt wird. 
Wir m\"ochten die Ergebnisse aller \textbf{extract-min}
Operationen finden. Das Problem ist offline, da wir die
gesamte Folge $S$ im Voraus kennen.

\begin{enumerate}
\item Betrachten Sie die folgende Operationsfolge
\[
4, 8, E, 3, E, 9, 2, 6, E, E, E, 1, 7, E, 5.
\]
Hierbei bedeutet eine Zahl $i$, dass \textbf{insert}$(i)$
ausgef\"uhrt werden soll, und $E$, dass \textbf{extract-min}
ausgef\"uhrt werden soll. Geben Sie die Ergebnisse der einzelnen
\textbf{extract-min}s an.

\item Wir m\"ochten nun einen Algorithmus f\"ur das Offline-Minimum
Problem entwickeln. Dazu unterteilen wir die Folge $S$ in Teilfolgen
\[
I_1, E, I_2, E, I_3, E, \dots, I_{m}, E, I_{m+1},
\]
wobei $I_j$ eine (m\"oglicherweise leere) Folge von \textbf{insert}s
darstellt und $E$ eine \textbf{extract-min} Operation.
Wir legen nun f\"ur jede Folge $I_j$ eine (m\"oglicherweise leere) 
Menge $K(j)$ an,
welche die Zahlen aus $I_j$ enth\"alt. Danach verwenden wir den
folgenden Algorithmus:
\begin{verbatim}
// em ist ein Feld mit m Elementen, dessen j-tes Element
// das Ergebnis des j-ten extract-mins speichern soll
for i := 1 to n do
    Finde die Menge K(j), die i enthaelt
    if j != m + 1 then
      em[j] <- i
      sei l > j der kleinste Index nach j,
        fuer den K(l) noch existiert 
      vereinige K(l) mit K(j), nenne das Ergebnis
        K(l) // K(j) existiert nun nicht mehr
\end{verbatim}
F\"uhren Sie den Algorithmus an dem Beispiel aus (a) aus. 
Beweisen Sie, dass der Algorithmus korrekt ist.

\item Beschreiben Sie, wie man den Algorithmus aus (b) effizient
mit einer Union-Find Struktur implementieren kann und analysieren 
Sie die Laufzeit.
\end{enumerate}

\AUFGABE{Amortisierte Analyse} {10 Punkte}

\begin{enumerate}
\item
Gegeben sei ein elektrisches Bin\"arz\"ahlwerk mit beliebig vielen 
Ziffern aus der Menge $\{0,1\}$. Das Umschalten einer Ziffer kostet
eine Stromeinheit. Wie viele Stromeinheiten kostet es insgesamt,
wenn man das Z\"ahlwerk von $0$ bis $n$ aufsteigend z\"ahlen 
l\"asst? Was sind die amortisierten Kosten pro Z\"ahlvorgang?
\item
Entwickeln und analysieren Sie eine Methode, um ein Array
zu verwalten, welches seine Gr\"o\ss{}e dynamisch \"andern kann
(ein solches Array ist zum Beispiel n\"utzlich, um einen Stack zu
implementieren). Die amortisierten Kosten pro Operation sollen 
konstant sein, und der Speicherplatz soll m\"oglichst gut
genutzt werden. K\"onnen Sie einen Trade-off zwischen der Laufzeit
und der Speicherplatznutzung finden?

\end{enumerate}

\AUFGABE{Wahrscheinlichkeitsrechnung und Hashing} {10 Punkte}
\begin{enumerate}
\item
Auf der ausgelassenen Weihnachtsfeier der Teilnehmer der HA-Vorlesung gibt es 
einen Julklapp (in Schwaben auch Wichteln genannt).  Die Teilnehmer bringen jeweils  
ein Geschenk mit, und alle Geschenke werden 
in einen gro\ss{}en Sack getan. Danach zieht jeder der Partyg{\"a}ste  
zuf{\"a}llig ein Geschenk aus dem Sack.  
Was ist die erwartete Anzahl der Leute,  
die ihr eigenes Geschenk ziehen? 

\item
Sei $N$ die Gr\"o\ss{}e einer gegebenen Hashtabelle und $n$ beliebig. 
Zeigen Sie,
dass f\"ur jede Schl\"usselmenge $K$ mit $|K| \ge (n-1)N + 1$ und jede
Hashfunktion $h: K \to \{0,\dots,N-1\}$ eine Menge $S \subseteq K$ mit
$|S| \geq n$ existiert, so dass alle Elemente von $S$ auf denselben Eintrag der
Hashtabelle abgebildet werden. 
Was bedeutet das f\"ur die worst-case Laufzeit von Hashing mit
Verkettung?

\end{enumerate}

\end{description}
\end{document}
