\documentclass[12pt]{article}
\usepackage{url}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\Bonus}[1]{\textbf{[#1 Points OPTIONAL Bonus Problem]}}
\newcommand{\Points}[1]{\textbf{[#1 Points]}}
\newcommand{\Name}[1]{\textbf{#1}}


\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2012 \\
	\rm
	Homework 7b  \\
	Due Tuesday, March 6
\end{center}

Throughout this assignment, you may appeal to any results that we've proved in class or on a previous assignment.  If you wish to use any such result, just state the result that you're using and indicate whether it was proved in class or on the previous assignment. 
\begin{enumerate}

\item \Points{20} \Name{Faster Implementations of Kruskal and Prim.}
Consider the minimum spanning tree problem again but now assume that all edge weights are integers
between 1 and $W$ where $W$ is some integer constant.
	\begin{enumerate}
		\item How fast can you make Kruskal's Algorithm run?  Explain your implementation and the running time.
		\item How fast can you make Prim's Algorithm run?  Explain your implementation and its running time.
	\end{enumerate}
	
\item \Points{10} \Name{Unique Spanning Trees.}
 Let $G$ be a connected undirected
graph in which each edge has a distinct edge weight (that is, no two edges have the same weight).
Prove that there is a \emph{unique} minimum spanning tree in the graph.  

\item \Points{20} \Name{Yet Another MST Algorithm!}
Professor Cy Kell has proposed the following algorithm for finding a minimum spanning tree in a connected graph in which \emph{all edges have distinct weights}:  Find a cycle in the graph.  Next, find the edge with maximum weight on that cycle and remove that edge.
Repeat this process until no more cycles remain.  At this point, Prof.~Kell claims, the remaining edges form a minimum spanning tree.   Your job is to prove it!  

\item \Points{15} \Name{Same Weights.}  Now, prove that Prof.~Kell's algorithm finds a MST even if the edge weights are not distinct.   


\end{enumerate}

\end{document}