\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 \#9 \hfill Due: 11/15/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{hw9.tex}, \texttt{hw9.pdf}, and \texttt{hw9.py} files via Canvas before 9:00 AM on the due date.
\section*{Section 11.3 (page 783)}
\subsection*{Exercise 4, a--c}
\subsection*{Exercise 4, d--e}
\subsection*{Exercises 12, 14}
\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.4 (page 796)}
\subsection*{Exercise 24}
\subsection*{Exercise 30, Part a}
\subsection*{Exercise 36}
%
% NOTE: Please delete the following section from your homework submission.
%
\section*{Python Exercises}
The goal of these exercises is to use depth first search to find the connected components in a simple undirected graph. You are to implement and test the functions \texttt{bfs}, \texttt{visit}, and \texttt{comps}. Submit your code in a separate \texttt{hw10.py} file. This file will be worth three homework exercises (i.e., 30\%).
\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 1 on Page 789 using the provided function definitions.
\medskip
\begin{lstlisting}
def dfs(G, v):
"""
Depth 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.
"""
def visit(G, T, v):
"""
Recursive subroutine for dfs that extends the tree T from vertex v.
This function modifies the parameter T, but does not return a value.
"""
\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], 1: [0, 3, 4], 2: [3], 3: [1, 2], 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], 1: [0, 3], 2: [3], 3: [1, 2]}
comps = [[0, 1, 2, 3], [4, 5, 6, 7]]
\end{verbatim}
\normalsize
\begin{lstlisting}
def test(G):
"""Tests the above functions using the given graph."""
print "graph =", G
T = dfs(G, 0)
print "stree =", T
C = comps(G)
print "comps =", C
print
if __name__ == "__main__":
# example graph from the comment at the top of the file
test({0: [1, 2],
1: [0, 3, 4],
2: [0, 3],
3: [1, 2],
4: [1, 5, 6],
5: [4],
6: [4, 7],
7: [6]})
# remove edge from 1 to 4; there should be two connected components
test({0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2],
4: [5, 6],
5: [4],
6: [4, 7],
7: [6]})
\end{lstlisting}
\end{document}