\documentclass[12pt]{article}

\usepackage{fullpage}

\begin{document}
\begin{center}
\bf
Algorithms Section 2\\
Spring 2003\\
\rm
Homework 7b\\
Due Tuesday, March 25 \\
\end{center}

\begin{enumerate}

\item \textbf{[25 Points] Implementing the Floyd-Warshall Algorithm!}
In this problem you will implement the Floyd-Warshall shortest path algorithm in your favorite
programming language.  For simplicity, you may assume that the graph will always have 5
vertices.  The program will then find the shortest path between every pair of vertices.
For each pair of vertices, $i$ and $j$, it must print the distance from $i$ to $j$ and then
the \emph{actual shortest path} from $i$ to $j$.

To see an example of how your program should behave, go to the directory \newline
\verb%~bthom/public_html/algorithms% on turing.  The file \verb%data% contains an adjacency matrix
for the graph shown on page 626 of our textbook.  Notice that the value $10000$ is being
used instead of $\infty$.  You can run the one we implemented for demonstration purposes, called \texttt{floyd}, by using
Unix redirection.  Simply type \verb%floyd < data%.

You should turn in a printout of your source code as well a script showing your program
running on the file \verb%data% in Belinda's directory.


\item \textbf{[10 Points] Finding a Negative Cost Cycle.}
In class we showed how the Bellman-Ford Algorithm can be used to detect if a
negative cost cycle exists in a directed graph.  Now explain how an actual negative cost cycle can
be found (that is, the vertices and edges in one such cycle can be printed out) if one exists.
Your algorithm needs to only find one such negative cost cycle.  Describe the algorithm
and analyze its running time.  Your algorithm should run in time polynomial in $V$ and $E$, but it's
not required to be the fastest possible algorithm for this problem.

\end{enumerate}

\end{document}

