\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{courseMacros}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 2001}{1 March 2001}{18}

\begin{center}
\Large{\bf Problem Set 5 (due March 8)}
\end{center}

{\bf 1. (30 points) Minimum spanning trees} 
\begin{itemize}
\item 
Suppose $T_1$ and $T_2$ are distinct minimum spanning trees for graph
$G$.  Let $(u,v)$ be the lightest edge (smallest weight edge) that is
in $T_2$ and is not in $T_1$.  Let $(x, y)$ be any edge that is in
$T_1$ and not in $T_2$.  Show that $w(x, y) \ge w(u,v)$.

\item
Prove that if the weights on the edges of a connected, undirected
graph are distinct, then there is a unique minimum spanning tree.
\end{itemize}

{\bf 2. (20 points) Bottleneck bandwidth} 

One can model a communication network by a weighted directed graph
$G$, in which the vertices of $G$ represent the nodes of the network,
the edges of $G$ represent the communication links of the network and
the weight of an edge is the bandwidth of the link.  We define the
{\em bottleneck bandwidth}\/ of a path $p$ as the bandwidth of the
minimum-bandwidth link in $p$.

Design and analyze an efficient algorithm to determine a path with the
largest bottleneck bandwidth from a given node $s$ to a given node $t$.
If no path from $s$ to $t$ exists, then your algorithm must indicate
so.  Briefly justify the correctness of your algorithm.  Analyze the
running time of your algorithm.  You may assume that the bandwidth of
every link is positive.  ({\em Hint:} Modify Dijkstra's algorithm.)

{\bf 3. (10 bonus points)} Exercise 7.12 part (a), page 378.

{\bf 3. (20 bonus points)} Exercise 7.49, page 384.  

\end{document}
