\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 \#5 \hfill Due: 10/11/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{hw5.tex} and \texttt{hw5.pdf} files via Canvas before 9:00 AM on the due date. As a reminder, late work will NOT be accepted.

\section*{Section 6.3 (page 413)}

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

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

\section*{Section 7.1 (page 451)}

\subsection*{Exercise 6}

\subsection*{Exercise 12}

\subsection*{Exercise 22}

\subsection*{Exercise 32}

\section*{Section 7.2 (page 466)}

\subsection*{Exercise 8: a, d, e}

\subsection*{Exercise 20}

\section*{Python Simulations}

\subsection*{Password Generator}
\textit{Your task is to implement a ``brute-force'' password cracker, i.e., one that systematically tries all possible passwords until the correct one is found. Use recursion and the \texttt{yield} statement to complete the function below.}

\medskip
\begin{lstlisting}
def words(length, alpha):
    """Generate all words of the given length from the given alphabet."""

if __name__ == "__main__":
    # generate all possible 4-digit pins
    for w in words(4, "0123456789"):
        print w
\end{lstlisting}

\subsection*{Relatively Prime}
\textit{The probability that two randomly chosen integers are relatively prime is $6 / \pi^2 \approx 0.6079$. Your task is to verify this theorem empirically by implementing the \texttt{test} function below. As a hint, you may want to review the Euclidean Algorithm (see Page 269).}

\medskip
\begin{lstlisting}
import random

def test(n, t):
    """Estimates and returns the probability that two random integers between
    0 and n are relatively prime by generating and checking t random pairs."""

if __name__ == "__main__":
    print test(1000000, 1000000)
\end{lstlisting}

\section*{Section 7.3 (page 475)}

\subsection*{Exercise 4}

\subsection*{Exercise 18}

\end{document}
