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

\head{CSU690}{Algorithms and Data}{Spring 2005}{30 March 2005}{15}

\begin{center}
\Large{\bf Problem Set 6 (due Wednesday, April 13)}
\end{center}

{\bf 1. (15 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.  You
may assume that the bandwidth of every link is positive.  ({\em Hint:}
Modify Dijkstra's algorithm.)

{\bf 2. (15 points) Arbitrage}

Problem 24-3, page 615.

{\bf 3. (10 points) Shortest paths on vertex-weighted graphs} 

Suppose you are given a connected undirected graph with weights on
vertices (rather than on edges) and you are asked to compute the
single-source shortest paths from a given source vertex.  Here, the
length of a path is defined as the sum of the weights on the vertices
comprising the path.  Give an algorithm for solving this problem by
reducing it to the standard single-source shortest paths problem on
directed graphs with weights on edges.

{\bf 4. (10 points) Bellman-Ford algorithm} 

Exercise 25.1-5, page 628.

{\bf 5. (10 points) Floyd-Warshall algorithm}

Exercise 25.2--1, page 634.

\end{document}