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

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{bis zum 07. 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{Implementierung von Kargers Algorithmus}{10 Punkte}

Beschreiben Sie, wie sich eine Iteration von Kargers Algorithmus (MINCUT1)
in $O(n)$ Zeit implementieren l\"asst (unter der Annahme, dass
\texttt{random(m)} $O(1)$ Zeit ben\"otigt).

\AUFGABE{Analyse des Karger-Stein Algorithmus}{10 Punkte}
\begin{enumerate}
\item Zeigen Sie, dass der Karger-Stein Algorithmus (MINCUT3) eine Laufzeit 
von $O(n^2 \log n)$ hat und mit Platzbedarf $O(n^2)$ implementiert werden kann. 

\item Folgern Sie mit Hilfe von Lemma 5 aus der Vorlesung, dass wir nun einen 
minimalen Schnitt in Zeit $O(n^2 \log^3 n)$ mit hoher Wahrscheinlichkeit ($\geq 
1- 1/n^c$) finden k\"onnen. 
\end{enumerate}


\AUFGABE{3-SAT}{10 Punkte}

Formulieren Sie eine Version des Algorithmus aus der Vorlesung f\"ur
das 3-SAT Problem. Analysieren Sie Ihren Algorithmus und bewerten
Sie das Ergebnis.

\end{description}

\end{document}
