%%% Fall 2004, HMW 6
\documentclass[11pt]{article}
 
\usepackage{epsf}
\usepackage{pslatex}

\setlength {\topmargin}{0in}
\setlength {\headheight}{0in}
\setlength {\headsep}{0cm}
\setlength {\textheight}{9in}
\setlength {\oddsidemargin}{0in}
\setlength {\evensidemargin}{0in}
\setlength {\textwidth}{6.5in}
\setlength {\parskip}{0cm} 


\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}
\thispagestyle{empty}

\begin{center}
{\bf \large ECE G205 Fundamentals of Computer Engineering} \\
{\bf Fall 2004} \\[0.5cm]
{\large \bf Homework 6: Due by Wednesday November 17 2004} \\
\end{center}

{\large
\vspace*{2cm}\noindent
\begin{itemize}

\item This test contains $2$ problems. They allow you to earn
$100$ points.

\item Show your work, as partial credit can be given. You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it. \textbf{Be neat}.

\item {\bf No late submissions will be accepted.}

\item Only homework returned in a 9in $\times$ 12in envelope
will be accepted. (If you cannot find such envelope, ask the
Instructor.) Please, write your name and the class name (ECE
G205) on the envelope (write clearly, please).

\item For the two problems below NO code has to be sent
  to the TAs.

\end{itemize}


\vspace*{3cm}
Write your name here:\ 
\hrulefill
}


\setcounter{page}{0}

%----------------------------------------------------------------------
\newpage
\begin{itemize}

\item {\bf Problem \# 1\ \ [50 points]}. 
Modify the Floyd-Warshal algorithm so that it returns
{\tt true} if and only if the input graph $G$ contains
negative cycles, {\tt false} otherwise.

%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 2\ \ [50 points]}. 
Write an algorithm whose input is the predecessor array
$\pi$ constructed by the Dijkstra algorithm and whose output
is a list of shortest paths from the source vertex to all of
the other vertices in the graph.

\end{itemize}

\end{document}
