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

\newcommand{\ZETTELNUMMER}{1}
\newcommand{\ABGABEDATUM}{am 21.\@ 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 {Sammelbilder} {10 Punkte}

Der letzte Hunger Games-Film kommt bald in die Kinos. Daher
gibt es in jeder Bircher-M\"uslipackung einen Aufkleber mit dem Bild
einer Figur aus dem Film.
Wir nehmen an, dass es insgesamt $n$ verschiedene
Sammelbilder gibt und dass jede neue M\"uslipackung
ein zuf\"allig gleichverteiltes Bild enth\"alt.
Uns interessiert, 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}.
   Dabei dauert jede Runde so lange, bis wir ein Sammelbild erhalten,
   welches wir vorher noch nicht besessen haben. 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 $\sum_{i=1}^{n}{1/i}= O(\log n)$ gilt.

  \textit{Hinweis}: Benutzen Sie Integralrechnung.

 \item Berechnen Sie $\text{E}[X]$.
\end{enumerate}
 
\AUFGABE{Rucksack}{10 Punkte}

Beim Rucksackproblem haben wir $n$ Gegenst\"ande gegeben.
Jeder Gegenstand hat ein \emph{Gewicht} $g_i$ und einen 
\emph{Wert} $w_i$. Au\ss{}erdem gibt es ein Maximalgewicht
$G$. Alle Eingaben sind nat\"urliche Zahlen.

Wir m\"ochten eine Teilmenge $I \subseteq \{1, \dots, n\}$ von
Gegenst\"anden finden,
so dass der Gesamtwert $\sum_{i \in I} w_i$ maximal ist,
unter der Nebenbedingung, dass das Maximalgewicht nicht \"uberschritten wird,
also $\sum_{i \in I} g_i \leq G$ gilt.

\begin{enumerate}
  \item Definieren Sie eine geeignete Entscheidungsvariante des Rucksackproblems und 
  zeigen Sie, dass sie NP-vollst\"andig ist.
  
  \emph{Hinweis}: Reduzieren Sie von SUBSET-SUM. 
  \item  
   Sei $W := \sum_{i=1}^n w_i$.
  Zeigen Sie, dass sich das Rucksackproblem in $O(nW)$ Schritten
    l\"osen l\"asst. Wieso ist das kein Widerspruch zu (a)?
  \item 
  Sei $\eps \geq 0$. Zeigen Sie, dass man in $\text{poly}(n,1/\eps)$
  Schritten eine L\"osung f\"ur das
  Rucksackproblem finden kann, deren Wert mindestens $(1-\eps) \text{OPT}$
  ist, wobei $\text{OPT}$ der Wert einer optimalen L\"osung ist.

  \emph{Hinweis}: Runden Sie die Werte geeignet und verwenden Sie (b). 
\end{enumerate}

\AUFGABE{Gewichteter Median}{10 Punkte}

Sei $S = \{s_1, s_2, \ldots, s_n\}$ eine Menge
von $n$ paarweise verschiedenen Elementen aus einem
total geordneten Universum. Seien $w_1$, $w_2$, $\ldots$,
$w_n$ positive Gewichte, so dass das Element $s_i$ Gewicht
$w_i$ hat. Es gelte $\sum_{i=1}^{n}w_i = 1$.
Der \emph{gewichtete Median} von $S$ ist das Element $s_k \in S$,
so dass gilt:
\[
\sum_{s_i < s_k} w_i \leq 1/2
\]
und
\[
\sum_{s_i > s_k} w_i < 1/2.
\]

\begin{enumerate}
\item
Angenommen, Sie haben eine Funktion, welche den gewichteten Median in
Zeit $T(n)$ bestimmt. Zeigen
Sie, wie man den (normalen) Median in Zeit $O(n) + T(n)$ 
berechnen kann.

\emph{Hinweis}: Finden Sie eine geschickte Wahl der Gewichte.

\item
Zeigen Sie, wie man den gewichteten Median in $O(n \log n)$ Zeit berechnen kann.

\emph{Hinweis}: Verwenden Sie einen geeigneten Sortieralgorithmus.

\item
Zeigen Sie, wie man den gewichteten Median in $O(n)$ Zeit finden kann, wenn
ein ein Linearzeitalgorithmus zum Finden des normalen Medians zur Verf\"ugung
steht.
\end{enumerate}
\end{description}
\end{document}
