\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\setlength{\parindent}{0pt}
\setlength{\parskip}{4pt}

\usepackage[usenames,dvipsnames]{color}
\usepackage{listings}
\lstset{
    language=python,
    basicstyle=\tt\small,
    commentstyle=\color{Green},
    keywordstyle=\color{blue},
    stringstyle=\color{Orange},
    keepspaces=true,
    showstringspaces=false,
    emphstyle=\color{Maroon},
    emph={__name__}
}

\begin{document}

\large
CS 228, HW \#8 \hfill Due: 11/08/2013
\begin{center}
\textbf{Name:} your name here
\par
\textbf{e-ID:} your e-ID here
\end{center}
\hrule
\normalsize

\bigskip
Unless otherwise specified, the exercises listed below are from the textbook \emph{Discrete Mathematics and Its Applications, 7th Ed.}, by Kenneth H.~Rosen. \textbf{Please show all of your work and explain your reasoning; don't just give the final answer.} Submit your \texttt{hw8.tex}, \texttt{hw8.pdf}, and \texttt{hw8.py} files via Canvas before 9:00 AM on the due date.

\section*{Section 10.5 (page 703)}

\subsection*{Exercise 4}

\subsection*{Exercise 30}

\section*{Section 10.6 (page 716)}

\subsection*{Exercise 4}

\subsection*{Exercise 14}

\subsection*{Exercise 18}

\section*{Python Exercise}

\textit{Extend Dijkstra's algorithm (on Page~712) to find the shortest path between two vertices in a weighted connected simple graph. To get started, implement Dijkstra's algorithm as-is and make sure it returns the shortest path length (it should be 13 in the provided test case). Then add code to keep track of the ``previous'' vertex for each vertex. Finally, construct the return value by traversing the previous vertices from $z$ back to $a$. Submit your code in a separate file named \texttt{hw8.py}.}

\medskip
\begin{lstlisting}
# global constant for Infinity
INF = float("inf")

def shortest(W, a, z):
    """Finds the shortest path between two vertices in a weighted connected
    simple graph.

    Args:
        W = adjacency matrix that contains the weight of each edge
        a = index of the source vertex
        z = index of the target vertex

    Returns:
        A list of vertices that represent the shortest path from a to z.
    """


if __name__ == "__main__":
    # example from Figure 4 on Page 713 of Rosen 7/e
    G1 = [[INF,   4,   2, INF, INF, INF],
          [  4, INF,   1,   5, INF, INF],
          [  2,   1, INF,   8,  10, INF],
          [INF,   5,   8, INF,   2,   6],
          [INF, INF,  10,   2, INF,   3],
          [INF, INF, INF,   6,   3, INF]]
    P1 = shortest(G1, 0, 5)
    # correct answer is a, c, b, d, e, z
    if P1 == [0, 2, 1, 3, 4, 5]:
        print P1, "is CORRECT"
    else:
        print P1, "is NOT correct"
\end{lstlisting}

\section*{Section 10.8 (page 733)}

\subsection*{Exercise 8}

\subsection*{Exercise 18}

\section*{Section 11.1 (page 755)}

\subsection*{Exercise 22}

\subsection*{Exercise 28}

\subsection*{Exercise 32}

\end{document}
