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

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{am 01. Dezember~2017 bis 10 Uhr 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, Datenstrukturen und Datenabstraktion}\hfill WS 17/18 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

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

\begin{enumerate}
\item
Programmieren Sie einen bin\"aren Heap mit $n$ Elementen, gespeichert 
als Array.  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}

Hierbei d\"urfen \texttt{decreaseKey} und
\texttt{delete} auf \texttt{bubble-up}
und \texttt{bubble-down} zur\"uckgreifen. 
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 ein 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 mindestens 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}

\AUFGABE{Hashing im Selbstversuch}{10 Punkte}

\begin{enumerate}
  \item  
    F\"ugen Sie nacheinander die Schl\"ussel 5, 28, 19, 15, 20, 33, 12, 17, 10
    in eine Hashtabelle der Gr\"o\ss{}e 9 ein. Die Hashfunktion sei
    $h(k) = k \bmod 9$. Die Konflikte werden mit Verkettung gel\"ost.
  \item 
    F\"ugen Sie nacheinander die Schl\"ussel 10, 22, 31, 4, 15, 28, 17, 88, 59
    in eine Hashtabelle der Gr\"o\ss{}e 11 ein. Die Hashfunktion sei
    $h(k) = k \bmod 11$. Die Konflikte werden durch
    offene Adressierung mit linearem Sondieren gel\"ost.
  \item 
    F\"ugen Sie nacheinander die Schl\"ussel 10, 22, 31, 4, 15, 29, 17, 88, 59
    in eine Hashtabelle der Gr\"o\ss{}e 11 ein. Die Konflikte werden
    durch Kuckuck gel\"ost, mit $h_1(k) = k \bmod 11$ und
    $h_2(k) = (k \bmod 13) \bmod 11$.
\end{enumerate}

Illustrieren Sie jeweils die einzelnen Schritte.

\emph{Hinweis}: Pseudocode f\"ur die Hashoperation findet
     sich auf der Website.
\end{description}

\noindent
\emph{Hinweis}:
Bitte formatieren Sie Ihre Abgaben mit \LaTeX\xspace oder einem
vergleichbaren elektronischen Textverarbeitungssystem. Ansonsten droht
der Abzug von bis zu 10\% der erreichbaren Punkte.


\end{document}
