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

\newcommand{\ZETTELNUMMER}{1}
\newcommand{\ABGABEDATUM}{bis zum 28. Oktober 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{$O$-Notation}{10 Punkte}

%\begin{enumerate}
%\item
%Zeigen Sie, dass $ \log n! = \Theta (n \log n)$ ist, und 
%folgern Sie daraus, dass f\"ur alle $c>0$ gilt, $c^n = O(n!)$.
%\item
Ordnen Sie die folgenden Funktionen so in einer Reihe 
$g_1, g_2, \dots, g_{10}$ an, dass $g_i\in\Omega(g_{i+1})$ f\"ur
$i = 1, \dots, 9$ gilt. 
Geben Sie auch an, wenn sogar $g_i = \Theta(g_{i+1})$ ist.
Begr\"unden Sie Ihre Antwort jeweils kurz 
(wir schreiben $\log n$ f\"ur $\log_2 n$). 

\begin{center}
\begin{tabular}{llllll}
$(\sqrt{2})^{\log n}$, & $n^2$, & 
$(\lceil \log n \rceil)!$,  & $\log^2n$, & $2^{(2^n)}$, \\
$n^{\frac{1}{\log n}}$, & $n^{\log\log n}$, & 
$\ln n$, & $2^n$, &
$4^{\log n}$. 
\end{tabular}
\end{center}
%\end{enumerate}

\AUFGABE {Sammelbilder} {10 Punkte}

Der n\"achste Harry-Potter-Spinoff steht kurz bevor. Daher
gibt es in jeder Bircher-M\"uslipackung einen  Aufkleber mit
dem Bild eines Zauberlehrlings.
Wir nehmen an, dass es insgesamt $n$ verschiedene
Sammelbilder gibt und dass jede neue M\"uslipackung
ein zuf\"allig gleichverteiltes Bild enth\"alt.
Wir wollen wissen, wie viele M\"uslipackungen wir kaufen m\"ussen, bis
unsere Sammlung vollst\"andig ist.

Sei also $X$ die Zufallsvariable, welche die
Anzahl der ben\"otigten M\"uslipackungen darstellt.
Wir wollen den Erwartungswert $\text{E}[X]$ berechnen.

\begin{enumerate}
 \item  Wir unterteilen den Sammelprozess in \emph{Runden}.
   Jede Runde dauert so lange, bis wir ein Sammelbild erhalten,
   das bisher noch nicht in unserem Besitz war. Am Ende
   der ersten Runde haben wir also ein Sammelbild, nach der zweiten
   Runde sind es zwei verschiedene Sammelbilder, usw. Die
   \emph{L\"ange} einer Runde ist die Anzahl der Packungen, 
   die wir im Laufe der Runde kaufen m\"ussen.

   Sei $X_i$ die Zufallsvariable, welche die L\"ange der $i$-ten Runde 
   darstellt. 
   Zeigen Sie, dass $\text{E} [X] = \sum_{i=1}^{n}\text{E}[X_i]$ ist.

 \item Berechnen Sie $\text{E}[X_i]$.

    \textit{Hinweis}: Verwenden Sie die geometrische Verteilung.

 \item Zeigen Sie, dass $\text{E}[X] = O(n\log n)$ ist.

    \textit{Hinweis}: Es gilt $\sum_{i=1}^{n}{\frac{1}{i}}= O(\log n)$.
\end{enumerate}
 
\hskip12cm \emph{Bitte wenden}

 \newpage

\AUFGABE {Leitern und Vasen}{10 Punkte}

Sie besitzen eine Leiter mit $n$ Sprossen sowie
eine wertvolle Ming-Vase. Die Sprossen der Leiter sind
von unten nach oben mit den Zahlen $1$ bis $n$ nummeriert.
Sie wissen, dass eine Sprosse $z \in \{0, \dots, n\}$ existiert,
f\"ur die gilt: L\"asst man die Vase von Sprosse $1$ bis
$z$ fallen, so bleibt sie ganz; l\"asst man die Vase von 
Sprosse $z+1$ bis $n$ fallen, so geht sie kaputt.
Ihre Aufgabe ist es, die Sprosse $z$ zu bestimmen.


\begin{enumerate}
\item Beschreiben Sie ein Verfahren, um $z$ mit Hilfe 
  einer \emph{Testvase} zu bestimmen. 
  Sie k\"onnen die
  Testvase von einer beliebigen Leitersprosse fallen lassen.
  Ist die Nummer der Sprosse kleiner oder gleich $z$, so bleibt die
  Testvase ganz; ist sie gr\"o\ss{}er als $z$, so geht die Testvase kaputt.
  Sobald die Testvase kaputt ist, kann man sie nicht mehr benutzen.

  Ihr Verfahren soll immer das richtige $z$ bestimmen und dabei mit
  einer Testvase auskommen. Wie oft m\"ussen Sie die Testvase fallen
  lassen?

\item Jetzt stehen Ihnen \emph{zwei} Testvasen zur Verf\"ugung.
  Wenn die erste Testvase kaputt ist, k\"onnen Sie die zweite verwenden.
  Wenn beide Testvasen kaputt sind, k\"onnen Sie keine weiteren
  Versuche mehr durchf\"uhren.

  Beschreiben Sie ein Verfahren zur Bestimmung von $z$, das immer
  funktionert und nur $O(\sqrt{n})$ Fallversuche
  ben\"otigt.
  
\item Nun haben Sie $k$ Testvasen. Zeigen Sie, wie
  man $z$ mit $O(k n^{1/k})$ Fallversuchen bestimmen
  kann. Was passiert f\"ur $k = \log n$?
\end{enumerate}

\end{description}
\end{document}
