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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{22. May 2017, in class}

\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{\R}{\mathbb{R}}



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


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Problem Set for 

\smallskip
\noindent
\large
\textbf{Advanced Algorithms II}\hfill Spring 2017 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost 

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Minimax Theorem}{10 Points}

Finish the proof of the minimax theorem by showing
that the two linear programs are in fact dual
to each other.

\AUFGABE{Bor\r{u}vka's Algorithm}{10 Points}

Let $G =(V, E)$ be a connected undirected weighted
graph with $n$ nodes and $m$ edges. 
Without loss of generality, suppose that all edges
weights are pairwise distinct.

\emph{Bor\r{u}vka's algorithm} for finding a minimum
spanning tree (MST) consists of a sequence of 
\emph{Bor\r{u}vka phases}.
In each phase, each node picks its incident edge with the minimum
weight.
The resulting edge set $F$ constitutes a spanning forest of $G$.
The components of this forest are contracted, resulting loops
are deleted, and if there are multiple edges, we keep only
the edge of smallest weight.
The algorithm stops as soon as there is only one node left.
The algorithm returns the union of all edge sets that were
contracted throughout its execution.
\begin{enumerate}
\item Show that Bor\r{u}vka's algorithm computes an MST.
\item Show that a Bor\r{u}vka phase can be implemented in time
$O(m')$, where $m'$ is the number of edges in the current graph.
\item Conclude that the algorithm runs in $O(\min\{m \log n, n^2\})$
  steps.
\item Recall that Prim's algorithm can find an MST in $G$ in time 
  $O(n \log n + m)$. Combine the algorithms of 
  Prim and Bor\r{u}vka in order to obtain an algorithm that 
  finds  $\text{MST}(G)$ in $O(m \log\log n)$ steps.

  \emph{Hint}: First, perform a suitable number of Bor\r{u}vka phases
    and then switch to Prim.
\end{enumerate}

\AUFGABE{MST-Verification} {10 Punkte}

Let $G =(V, E)$ be a connected undirected weighted graph with
$n$ nodes and $m$ edges, such that all edge weights are
pairwise distinct.

Let $A \subseteq E$ be acyclic. An edge $e \in E$ is \emph{$A$-light},
if either (i) $A \cup \{e\}$ is acyclic; or (ii) the unique cycle
$C$ in $A \cup \{e\}$ contains an edge that has a larger weight
than $e$.

\begin{enumerate}
  \item  Show that $A$ is an MST for $G$ if and only if
    $E \setminus A$ contains no $A$-light edges. 
  \item  Show that $e \in E$ is 
    $A$-light if and only if $e \in \text{MSF}(V, A \cup \{e\})$,
    where $\text{MSF}$ denotes the minimum spanning \emph{forest}.
\end{enumerate}


\end{description}
\end{document}
