\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath}
\usepackage{listings}
\usepackage[usenames,dvipsnames]{color}
\lstset{
    language=python,
    basicstyle=\tt\small,
    commentstyle=\color{Green},
    keywordstyle=\color{blue},
    stringstyle=\color{Orange},
    keepspaces=true,
    showstringspaces=false,
    emphstyle=\color{Maroon},
    emph={__name__}
}

\setlength{\parindent}{0pt}
\setlength{\parskip}{4pt}


\begin{document}

\large
CS 228, HW \#8 \hfill Due: 3/28/2014

\textbf{Name:} your name here

\textbf{e-ID:} your e-ID here

\textbf{Acknowledgement statement:}


\hrule
\normalsize

\section*{Section 10.1 (page 649)}

\subsection*{Exercise 10}

\subsection*{Exercise 20}

\section*{Section 10.2 (page 665)}

\subsection*{Exercise 4}

\subsection*{Exercise 10}

\section*{Section 10.3 (page 675)}

\subsection*{Exercise 4}

\subsection*{Exercise 8}

\subsection*{Exercise 34 and 36}

\section*{Section 10.4 (page 689)}

\subsection*{Exercise 2, a--d}

\subsection*{Exercise 14, a--c}

%
% NOTE: Please delete the following page from your homework submission.
%

\newpage

\section*{Python Exercises}

Implement the following functions in Python. Your code does not need
to handle multigraphs. \textbf{Submit your code in a separate file
  named hw8.py.}
\subsection*{Degree Functions}

\begin{lstlisting}
def in_degree(vertices, edges):
    """Computes the in-degree of each node in a directed graph.

    Example: in_degree( [1, 2, 3] , [(1, 2), (2, 1), (3, 2)] )
    Returns: {1: 1, 2: 2, 3: 0}
    """
    return {}

def out_degree(vertices, edges):
    """Computes the out-degree of each node in a directed graph.

    Example: out_degree( [1, 2, 3] , [(1, 2), (2, 1), (3, 2)] )
    Returns: {1: 1, 2: 1, 3: 1}
    """
    return {}
\end{lstlisting}

\subsection*{Adjacency Matrix}

\begin{lstlisting}
def vertices_edges(matrix):
    """
    Constructs vertex list and edge list from an adjacency matrix.

    The first return value is a list of vertices, the second is a list
    of edges. 

    Example: vertices_edges([[0, 1, 0], [1, 0, 0], [0, 1, 0]])
    Returns: [1, 2, 3], [(1, 2), (2, 1), (3, 2)]
    """
    return [], []
\end{lstlisting}

\subsection*{Testing Code (You don't need to modify this.)}
\begin{lstlisting}
def test_vertices_edges():
    """ Testing code for vertices_edges function. """
    A = [[0, 1, 0], 
         [1, 0, 0], 
         [0, 1, 0]]

    B = [[0, 1, 0, 1], 
         [1, 1, 0, 1], 
         [0, 0, 0, 0], 
         [1, 0, 0, 1]]

    verticesA, edgesA = vertices_edges(A)
    verticesB, edgesB = vertices_edges(B)
    
    print "A:", verticesA, edgesA
    print "B:", verticesB, edgesB

def test_degree():
    """ Testing code for in_degree and out_degree. """

    verticesA = [1, 2, 3]
    edgesA = [(1, 2), (2, 1), (3, 2)]

    verticesB = [1, 2, 3, 4]
    edgesB = [(1, 2), (1, 4), (2, 1), (2, 2), (2, 4), (4, 1), (4, 4)]

    print "in-degrees for A:", in_degree(verticesA, edgesA)
    print "out-degrees for A:", out_degree(verticesA, edgesA)
    print "in-degrees for B:", in_degree(verticesB, edgesB)
    print "out-degrees for B:", out_degree(verticesB, edgesB)

if __name__ == "__main__":
    test_vertices_edges()
    test_degree()
\end{lstlisting}

\end{document}

