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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{am 21. November 2013 vor der Vorlesung in 
                          die jeweiligen Tutorenf\"acher}

\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})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Algorithmen und Programmierung III} \\[0.5ex]
\normalsize
Wolfgang Mulzer \hfill WiSe 2013/14

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Bin\"are Heaps}{10 Punkte}
\begin{enumerate}
  \item  
    Wie viele Elemente enth\"alt ein bin\"arer Heap der H\"ohe $h$
    mindestens? Wie viele sind es h\"ochstens?
    Beweisen Sie, dass ein bin\"arer Heap mit $n$ Elementen
    H\"ohe $\Theta(\log n)$ hat. (\emph{Achtung:}
    Wir z\"ahlen die H\"ohe und die Ebenen ab $0$.)
  \item 
    Wo kann in einem bin\"aren Heap das zweitkleinste
    Element stehen? Wie ist es mit dem drittkleinsten
    Element? Geben Sie allgemein an, auf welchen Ebenen eines
    bin\"aren Heaps mit $n$ Elementen sich das $k$.~kleinste Element 
    befinden kann
    (Sie d\"urfen annehmen, dass alle Ebenen voll besetzt sind).
  \item 
    Veranschaulichen Sie die bottom-up Heapkonstruktion mit dem Array
    \texttt{[7, 6, 5, 3, 1, 4, 2, 8]}. 
    
    \emph{(freiwillig, 5 Zusatzpunkte)}
    Angenommen, wir f\"ugen $n$ Elemente nacheinander in einen
    anfangs leeren Heap ein. Zeigen Sie, dass dies im
    worst-case $\Omega(n \log n)$ Zeit ben\"otigt.

    \emph{Achtung}: Anfangs braucht das Einf\"ugen wesentlich
      weniger als $\log n$ Schritte.
\end{enumerate}


\AUFGABE{Implementierung weiterer Heap-Operationen}{10 Punkte}

\begin{enumerate}
\item
Programmieren Sie einen bin\"aren Heap mit $n$ Elementen, gespeichert als Array,
in Java.
Implementieren Sie au\ss{}erdem 
die folgenden Operationen mit jeweils einer Laufzeit von
$O(\log n)$:

\begin{itemize}
\item {\texttt{decreaseKey$(i,k)$}}:  Setze das Element an Position $i$ auf
  den Wert $k$ und stelle die Heapeigenschaft wieder her (Vorbedingung:
  $k$ ist kleiner gleich  dem alten Element an Position $i$).
\item {\texttt{delete$(i)$}}:  L\"osche das Element an der Position  $i$ 
und stelle die Heapeigenschaft wieder her.
\end{itemize}

Vermeiden Sie Redundanzen, indem Sie bereits vorhandene 
Funktionen nutzen. Begr\"unden Sie kurz Korrektheit 
und Laufzeit.

\item
Wir wollen das Interface \texttt{PriorityQueue} aus der Vorlesung
um die Operationen aus (a) erweitern. Erkl\"aren Sie kurz, 
warum wir zur effizienten 
Implementierung einen ``Zeiger'' in die 
Datenstruktur ben\"otigen (d.h., warum ist es keine gute
Idee, an \texttt{decreaseKey} nur das alte und das neue
Element zu \"ubergeben, selbst wenn jedes Element nur 
einmal in der Datenstruktur vorkommt?). 

Wie k\"onnen wir solche
Zeiger implementieren, so dass das Geheimnisprinzip gewahrt bleibt?
F\"uhren Sie eine Interface \texttt{Position} ein, das einen 
Zeiger in die Datenstruktur repr\"asentiert.
Erl\"autern Sie knapp, wie man das Interface 
\texttt{PriorityQueue} modifizieren kann, um \texttt{Position} 
zu benutzen.  Welche Schwierigkeiten ergeben sich dabei?
Skizzieren Sie kurz einen  L\"osungsansatz.
(Bei dieser Teilaufgabe m\"ussen Sie nichts programmieren.)
\end{enumerate}

\AUFGABE{Elementare Wahrscheinlichkeitsrechnung}{10 Punkte}

Auf einem Tisch stehen $N$ Kisten. In diese Kisten werden
nacheinander unabh\"angig voneinander $n$ B\"alle  geworfen, 
wobei jede Kiste mit
gleicher Wahrscheinlichkeit  getroffen wird.

\begin{enumerate}
\item Berechnen Sie die Wahrscheinlichkeit, dass 
Kiste $i$ leer ist.
Sei $Y_i$ die Zufallsvariable, die den Wert $1$ annimmt, falls Kiste $i$
leer ist, und $0$ sonst.  Geben Sie auch den Erwartungswert $E[Y_i]$ an.

\item Sei $X$ die Zufallsvariable, welche die Anzahl von leeren Kisten angibt.
  Berechnen Sie den Erwartungswert von $X$ mit Hilfe der Erwartungswerte
  $E[Y_i]$.

\item 
Geben Sie eine m\"oglichst gute Schranke $f(N)$ an, so
dass gilt: wenn  $n \geq f(N)$,
dann ist die Wahrscheinlichkeit, dass eine Kiste mindestens zwei
B\"alle enth\"alt, gr\"o\ss{}er als $1/2$. 

\emph{Hinweis}:
Stellen Sie sich vor, die $n$ B\"alle werden nacheinander
in die Kisten geworfen. Was ist die Wahrscheinlichkeit, 
dass der n\"achste Ball in einer leeren Kiste landet, 
wenn alle vorherigen B\"alle in einer leeren Kiste
gelandet sind?
Verwenden Sie die ungemein n\"utzliche Absch\"atzung 
$1+x \leq e^x$, welche f\"ur alle $x \in \mathbb{R}$ gilt.

\item
Professor Pinocchio hat eine Idee, um Hashtabellen 
zu vereinfachen. Wenn wir die Zahl $N$ der
Pl\"atze in der Hashtabelle im Verh\"altnis zur Anzahl 
der zu speichernden Eintr\"age $n$ gro\ss{} genug
w\"ahlen, sollte die Wahrscheinlichkeit, dass Kollisionen
auftreten, verschwindend gering werden (unter der Annahme, dass sich die
Hashfunktion wie eine zuf\"allige Funktion verh\"alt).
Dann k\"onnte man auf die Kollisionsbehandlung verzichten.
In Anbetracht von (c), was halten Sie von dem Vorschlag?
(Wenn Sie Teil (c) nicht gel\"ost haben, dann bearbeiten
Sie diesen Teil unter der Annahme, dass $f(N)=N^{1/3}$ ist.
Achtung: Das ist nicht die L\"osung f\"ur (c).)
\end{enumerate}

\end{description}
\end{document}
