\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 \#10 \hfill Due: 4/18/2014

\textbf{Name:} your name here

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

\textbf{Acknowledgment statement:}


\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{hw10.tex} and \texttt{hw10.pdf} files via Canvas before 1:00 PM
on the due date. As a reminder, late work will NOT be accepted.


\section*{Section 11.3 (page 783)}


\subsection*{Exercises 12, 14}

\subsection*{Exercise 16, b--c}

\subsection*{Exercise 24, a--b}

\textit{Write each step of the calculation on a separate line, and show with parentheses the operation that is applied. Note that each step always involves the first occurrence of an operator symbol.}

\begin{verbatim}
Part A:
= 5 (2 1 -) - 3 1 4 + + *
= ...
\end{verbatim}



\section*{Section 11.5 (page 796)}

\subsection*{Exercise 4}
\emph{For this exercise and the next, your answer should be in the
  same tabular form as Figures 4b and 5b on pages 800 and 801.  Use
  alphabetical order to break ties when there are multiple edges that
  could be selected: edge \{a, b\} should be selected before \{a, e\}
  etc. }


\subsection*{Exercise 8}



%
% NOTE: Please delete the following section from your homework submission.
%
\newpage
\section*{Python Exercises}

The goal of these exercises is to use breadth first search to find the connected components in a simple undirected graph. You are to implement and test the functions \texttt{bfs} and \texttt{comps}. Submit your code in a separate \texttt{hw10.py} file. This file will be worth three homework exercises.

\subsection*{Part 0: Header Comment}

\begin{lstlisting}
#
# In this assignment, "G" is an undirected graph represented by an adjacency
# list that specifies all vertices by index. For example, consider the graph:
#
#   0 -- 1 -- 4 -- 5
#   |    |    |
#   2 -- 3    6 -- 7
#
# The corresponding adjacency list is implemented as a dictionary of lists:
#
#   {0: [1, 2],
#    1: [0, 3, 4],
#    2: [0, 3],
#    3: [1, 2],
#    4: [1, 5, 6],
#    5: [4],
#    6: [4, 7],
#    7: [6]}
#
\end{lstlisting}

\subsection*{Part 1: Depth First Search}

Implement Algorithm 2 on Page 791 using the provided function definition.

\medskip
\begin{lstlisting}
def bfs(G, v):
    """
    Breadth first search of G starting from v. This function returns the
    spanning tree T, which has the same format as G. Note that T should
    not include all vertices if G is not connected.
    """
\end{lstlisting}

\subsection*{Part 2: Connected Components}

The basic idea of this function is (1) for each vertex not yet in a spanning tree, (2) find the spanning tree from that vertex. In a totally unconnected graph of $n$ vertices, you will have $n$ spanning trees.

\medskip
\begin{lstlisting}
def comps(G):
    """
    Finds and returns the connected components of G. Each one is represented as
    a list of vertices, in sorted order. This function returns a list of lists.
    """
\end{lstlisting}

\subsection*{Part 3: Additional Test Cases}

The sample solution has the following output for the test cases provided below. After you get the same results, go back and write your own test cases. For example, does your solution still work if G has only one vertex? What if G has five vertices but no edges? For full credit, you must write at least three additional test cases.

\footnotesize
\begin{verbatim}
graph = {0: [1, 2], 1: [0, 3, 4], 2: [0, 3], 3: [1, 2], 4: [1, 5, 6], 5: [4], 6: [4, 7], 7: [6]}
stree = {0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1, 5, 6], 5: [4], 6: [4, 7], 7: [6]}
comps = [[0, 1, 2, 3, 4, 5, 6, 7]]
graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2], 4: [5, 6], 5: [4], 6: [4, 7], 7: [6]}
stree = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}
comps = [[0, 1, 2, 3], [4, 5, 6, 7]]
\end{verbatim}




\end{document}

