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

\newcommand{\ZETTELNUMMER}{1}
\newcommand{\ABGABEDATUM}{on 03. May 2016 in the tutorial session}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem~\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. Assignment on 

\smallskip
\noindent
\large
\textbf{Computational Complexity Theory}\hfill SoSe 2016 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Claudia Dieckmann

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE {Collecting Stickers} {10 points}

The next installment of the Star Wars series will soon hit the
movie theaters. Thus, every bag of Bircher-M\"uesli contains
a sticker with the likeness of a Star-Wars-character.
We assume that there are $n$ different stickers, and that
each bag contains a sticker that is chosen uniformly at
random.
We would like to know how many bags of M\"uesli we need to buy
until our collection is complete.

Let $X$ be the random variable that represents the required
number of bags.
The goal is to find the expected value
$\text{E}[X]$.

\begin{enumerate}
 \item  We subdivide the process into \emph{rounds}.
   A round ends as soon as we obtain a sticker that we have
   not seen before. Thus, the first round ends with the first sticker,
   the second round ends as soon as we have two distinct stickers, and so
   on.
   The  
   \emph{length} of a round is defined as the number of M\"uesli bags that we need
   to buy during that round. 

   Let $X_i$ be the random variable that represents the length of round $i$.
   Show that $\text{E} [X] = \sum_{i=1}^{n}\text{E}[X_i]$.

 \item Find $\text{E}[X_i]$.

    \textit{Hint}: $X_i$ follows a geometric distribution.

 \item Conclude that $\text{E}[X] = O(n\log n)$.

    \textit{Hint}: $\sum_{i=1}^{n}{(1/i)}= O(\log n)$.
\end{enumerate}
 

\AUFGABE{Knapsack}{10 points}

In the  knapsack problem, we are given $n$ items.
Each item has a \emph{weight} $g_i$ and a 
\emph{value} $w_i$. Furthermore, we have a maximum weight
$G$. All inputs are positive integers.

We would like to find a set $I \subseteq \{1, \dots, n\}$ of
items,
such that the total value $\sum_{i \in I} w_i$ is maximum,
subject to the constraint that the total weight is at most $G$,
i.e., $\sum_{i \in I} g_i \leq G$.

\begin{enumerate}
  \item Define an appropriate decision version for the knapsack problem and show that
  it is NP-complete.
  
  \emph{Hint}: Reduce from SUBSET-SUM. 
  \item  
   Let $W := \sum_{i=1}^n w_i$.
  Show that the knapsack problem can be solved in $O(nW)$ time.
    Why does this not contradict (a)?
  \item 
  Let $\eps \geq 0$. Show that we can find in $\text{poly}(n,1/\eps)$ time
  a solution for the knapsack problem 
  with value at least $(1-\eps) \text{OPT}$,
  where $\text{OPT}$ is the value of an optimal solution.

  \emph{Hint}: Round appropriately and use (b). 
\end{enumerate}

\AUFGABE{NP-completeness}{10 points}

Show that for every $\eps > 0$, there exists an NP-complete
problem that can be solved deterministically in $O\big(2^{n^{\eps}}\big)$ steps. 

\emph{Hint}: Show that SAT remains
NP-complete if you add a polynomial number of ``garbage bits'' to
the input.
\end{description}
\end{document}
