\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 \#7 \hfill Due: 10/25/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{hw7.tex}, \texttt{hw7.pdf}, and \texttt{hw7.py} files via Canvas before 9:00 AM on the due date.

\section*{Section 10.1 (page 649)}

\subsection*{Exercise 10}

\subsection*{Exercise 26}

\section*{Section 10.2 (page 665)}

\subsection*{Exercise 4}

\subsection*{Exercise 18}

\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 two functions in Python. Write additional test cases to verify that your solutions can handle graphs with multiple edges and loops (i.e., pseudographs). \textbf{Submit your code in a separate file named hw7.py.}

\subsection*{Degree Function}

\begin{lstlisting}
def degree(nodes, edges):
    """Computes the degree of each node in an undirected graph.

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

\subsection*{Matrix Function}

\begin{lstlisting}
def matrix(nodes, edges):
    """Constructs an adjacency matrix for an undirected graph.

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

\subsection*{Test Cases}

\begin{lstlisting}
if __name__ == "__main__":

    # pretty-print the results
    from pprint import pprint

    # example nodes and edges
    N = [1, 2, 3, 4, 5]
    E = [(1,2), (1,3), (1,5), (3,4), (3,5), (4,5)]
    print
    pprint(degree(N, E))
    print
    pprint(matrix(N, E))

    # another example graph
    N = ['A', 'B', 'C', 'D', 'E']
    E = [('A','B'), ('A','C'), ('A','D'), ('B','A'), ('C','D'), ('D','D')]
    print
    pprint(degree(N, E))
    print
    pprint(matrix(N, E))
\end{lstlisting}

\end{document}
