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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{am 28.\@ April 2015 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}}
\newcommand{\eps}{\varepsilon}


\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


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

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik II}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Lena Schlipf, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Die Effektivit\"at randomisierter Algorithmen}{10 Punkte}

Sei $A$ ein Array mit $n$ Eintr\"agen. Wir wissen, dass $A$ einen
bestimmen Schl\"ussel $k$ enth\"alt, und  wir wollen die Position
von $k$ bestimmen.

\begin{enumerate}
  \item Zeigen Sie, dass jeder deterministische Algorithmus im 
  schlimmsten Fall mindestens $n-1$ Zugriffe auf $A$ durchf\"uhren 
  muss, um die Position von $k$ zu finden.
  \item  Entwickeln Sie einen randomisierten Algorithmus, der das Problem mit
    $(n+1)/2$ erwarteten Zugriffen l\"ost.
\end{enumerate}

\AUFGABE {Alternativer Beweis der Chernoff-Schranke} {10 Punkte}

In dieser Aufgabe betrachten wir Chv{\'a}tals Beweis f\"ur eine
Variante der Chernoff Schranke.
Sei $B(n,p)$ die Zufallsvariable, welche die Erfolge
in einer Folge von $n$ unanbh\"angigen Bernoulli Versuchen
mit Erfolgswahrscheinlichkeit $p$ z\"ahlt.

\begin{enumerate}
\item Zeigen Sie: f\"ur alle $x \geq 1$ ist
\[
\Pr[B(n,p) \geq k] \leq \sum_{i = 0}^{n} \binom{n}{i} p^i (1-p)^{n-i} x^{i-k}.
\]
\item Benutzen Sie den Binomialsatz, um eine geschlossene obere Schranke f\"ur
 die Wahrscheinlichkeit $\Pr[B(n,k) \geq k]$ zu erhalten.
\item Finden Sie den eine bestm\"ogliche Wahl f\"ur $x$.
\item Folgern Sie: f\"ur $t \geq 0$ gilt
\[
\Pr[B(n,p) \geq (p+t)n] \leq \left( \left(\frac{p}{p+t}\right)^{p+t}
\left(\frac{1-p}{1-p-t}\right)^{1-p-t}\right)^n.
\]
  Interpretieren Sie Ihr Ergebnis.
\end{enumerate}

\AUFGABE{Anwendung der Chernoff-Schranke}{10 Punkte}

Angenommen, Sie haben eine gezinkte M\"unze, die mit einer
unbekannten Wahrscheinlichkeit $p > 0$ Zahl zeigt.
Seien $\eps > 0$ und $\delta > 0$. 
Entwerfen und Analysieren Sie einen Algorithmus, 
der mit Wahrscheinlichkeit mindestens $1-\delta$ eine
\emph{additive} $\eps$-Approximation 
f\"ur $p$ liefert (d.h., wir wollen eine Sch\"atzung
$\tilde p$, so dass $\Pr[|p-\tilde p| > \eps] \leq \delta$
gilt). 
L\"osen Sie die gleiche Aufgabe bez\"uglich einer \emph{multiplikativen}
Approximation (d.h.,
$\Pr[|p-\tilde p| > \eps p] \leq \delta$).
Analysieren Sie die Laufzeit Ihres Algorithmus.


\end{description}
\end{document}
