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

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{bis zum 28. November 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{\eps}{\varepsilon}
\newcommand{\E}{\mathbf{E}}
\renewcommand{\Pr}{\mathbf{Pr}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\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{Randomisierte Algorithmen}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Paul Seiferth, Max Willert

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Coverage Algorithmus}{10 Punkte}

Sei $U$ ein endliches Universum und 
$S_1,\dots, S_m \subseteq U$. 
Wir kennen $|S_i|$, f\"ur $i = 1, \dots, m$, und 
wir m\"ochten ein
FPRAS f\"ur die Gr\"o\ss{}e der Vereinigung
$S =  \bigcup_{i=1}^m S_i$ erhalten.

Wir nehmen an, dass wir f\"ur alle  $S_i$
effizient ein zuf\"alliges Element $x \in S_i$ ziehen k\"onnen.
Wir nehmen auch an, dass wir f\"ur $x \in U$ effizient  die Anzahl $c(x)$
der Mengen $S_i$ bestimmen k\"onnen, die $x$ enthalten.

\begin{enumerate}
\item  Betrachten Sie folgendes Experiment:
  W\"ahle zuf\"allig $I \in \{1, \dots, m\}$ mit
    \[
      \Pr[I = i] = \frac{|S_i|}{\sum_{j = 1}^m |S_j|}.
    \]
  W\"ahle dann ein zuf\"alliges $x \in S_I$ und setze $Z = 1/c(x)$.
  Zeigen Sie, dass $Z$ einen 
  \emph{Sch\"atzer} f\"ur $|S|/\sum_{j = 1}^m |S_j|$ 
  liefert, d.h., 
  \[
    \text{E}[Z] = \frac{|S|}{\sum_{j = 1}^m |S_j|}.
  \]
\item Benutzen Sie (a), um einen Algorithmus zu
  entwickeln, der bei Eingabe $\eps, \delta > 0$ einen Wert 
  $A$ ausgibt mit
  \[
    \Pr[(1-\eps)|S| \leq A \leq (1+ \eps) |S|] \geq 1-\delta.
  \]
  Die Laufzeit sollte polynomiell sein in $m$, $1/\eps$ und 
  $\log(1/\delta)$.


  \emph{Hinweis}: Benutzen Sie folgendes \emph{Sampling Lemma}: 
    Sei $\alpha > 0$ und $Z$ eine Zufallsvariable mit
    $Z \in [\alpha,1]$ und $\text{E}[Z] = \mu$.
    Seien $\eps, \delta \geq 0$ gegeben. 
    F\"ur $N = (4/\alpha\eps^2) \ln (2/\delta)$ 
    seien $Z_1, \dots, Z_N$ unabh\"angige Kopien von $Z$ und
    $W = (1/N)\sum_{i = 1}^N Z_i$. 
    Dann gilt
    \[
      \Pr[|W - \mu| > \eps\mu ] \leq \delta.
    \]

\item Benutzen Sie (b), um das DNF-Counting Problem zu
  l\"osen: Gegeben eine aussagenlogische Formel 
  $\Psi = C_1 \vee C_2 \vee \dots \vee C_m$ in
  disjunktiver Normalform, finde ein FPRAS f\"ur die Anzahl 
  der erf\"ullenden
  Belegungen von $\Psi$.
\end{enumerate}


\AUFGABE{\#RUCKSACK}{20 Punkte}

Entwickeln Sie ein FPRAS f\"ur das Problem \#RUCKSACK:

\textbf{Gegeben}: 
$w_1, \dots, w_n, B \in \N$ mit 
$w_i \leq B$, f\"ur $1 \leq i \leq n$.


\textbf{Gesucht}: $|\mathcal{S}|$, f\"ur  
$\mathcal{S} = \big\{ I \subseteq \{1, \dots, n\} \mid \
\sum_{i \in I}{w_i} \leq B \big\}$.

Gefragt ist also die Anzahl der zul\"assigen 
Rucksackf\"ullungen. 

\begin{enumerate}
\item 
Beschreiben Sie einen Algorithmus, 
der \#RUCKSACK in $O(nB)$ Zeit mit dynamischem Programmieren l\"ost.

\emph{Hinweis}: Betrachten Sie
f\"ur $1 \leq i \leq n$, $1 \leq b \leq B$
die Anzahl $F(i, b)$ der zul\"assigen Rucksackf\"ullungen
f\"ur die Gewichte $w_1, \dots, w_i$ und Gesamtkapazit\"at $b$.

\item Wir setzen $w_i' = \lfloor n^2\frac{w_i}{B} \rfloor$. Sei
\[
\mathcal{S}' = \big\{ I \subseteq \{1, \dots, n\} \mid \
\sum_{i \in I}{w_i'} \leq n^2 \big\}.
\]
Zeigen Sie: (i) Wir k\"onnen $|\mathcal{S}'|$ in $O(n^3)$ Zeit finden; 
(ii) es gilt $\mathcal{S} \subseteq \mathcal{S}'$;  und
(iii) es gilt $|\mathcal{S}'| \leq (n+1) |\mathcal{S}|$.

\emph{Hinweis zu (iii)}: Zeigen Sie, dass
$|\mathcal{S}' \setminus \mathcal{S}| \leq n|\mathcal{S}|$
ist. \"Uberlegen Sie zun\"achst, dass f\"ur jede Rucksackf\"ullung 
$I \in \mathcal{S}' \setminus \mathcal{S}$ gilt: das schwerste
Element $j$ in $I$ hat $w_j > B/n$, also $w_j' \geq n$. Zeigen Sie dann,
dass $I \setminus \{j\}$ in $\mathcal{S}$ liegt.
\item 
  Beschreiben Sie einen polynomiellen Zufallsalgorithmus,
  der ein zuf\"allig gleichverteiltes Element 
  aus $\mathcal{S}'$ liefert.

\emph{Hinweis}: Erzeugen Sie $I \in \mathcal{S}'$ zuf\"allig,
indem Sie die Elemente $n, n-1,  \dots, 1$ in dieser Reihenfolge
durchgehen, und f\"ur jedes Element zuf\"allig entscheiden,
ob es in $I$ enthalten sein soll. Benutzen Sie die Tabelle,
die durch das dynamische Programm in (a) erstellt wurde, um
die richtigen Wahrscheinlichkeiten zu finden.

\item Benutzen Sie die Monte-Carlo Methode, um ein
FPRAS f\"ur $|\mathcal{S}|$ zu entwickeln.
\end{enumerate}


\AUFGABE{Des Spielers Bankrott}{freiwillig, 10 Zusatzpunkte}

Seien $a, b \in \N$. Betrachten Sie den Pfad mit Knotenmenge
$\{0, 1, 2, \dots, a+b\}$, nummeriert von links nach rechts.
Nehmen Sie an, wir beginnen bei Knoten $a$ und gehen
in jedem Schritt jeweils mit Wahrscheinlichkeit $1/2$ nach links 
oder nach rechts. Bestimmen Sie die Wahrscheinlichkeit, dass
wir den Knoten $0$ vor dem Knoten $a+b$ erreichen.


\end{description}

\end{document}
