\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2014}{28 September 2014}{7}

\begin{center}
\Large{\bf Problems of the Week -- 5 and 6}
\end{center}

{\bf POW-5: Maximum-weight edge of a spanning tree}

Show the maximum weight of an edge in any minimum spanning tree is
minimum, among all spanning trees of G.

{\bf POW-6: Matroids and minimum spanning trees}

In matroid theory, we have covered the greedy algorithm for
maximum-weight independent sets.  Show that the problem of finding a
minimum-weight maximal independent set of a given matroid can be
reduced to the problem of finding a maximum-weight independent set in
a matroid.  Use this reduction to argue that the minimum spanning tree
problem can be presented as a weighted-matroid problem.

\end{document}