<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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 \#7 \hfill Due: 3/21/2014

\textbf{Name:} your name here

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

\textbf{Acknowledgement statement:}


\hrule
\normalsize


\section*{Python Exercises}

\textit{Complete the four Python functions defined below, which represent properties of relations (refer to Pages 576--578). The parameter M is a zero-one matrix representing a relation on a finite set, and is implemented in Python using a list of lists of integers. \textbf{Your implementation must not modify the contents of M.}}

\subsection*{Reflexive, symmetric}
\begin{lstlisting}
def reflexive(M):
    """Returns True if the relation M is reflexive, False otherwise."""
    return False

def symmetric(M):
    """Returns True if the relation M is symmetric, False otherwise."""
    return False
\end{lstlisting}

\subsection*{Transitive property}

\begin{lstlisting}
def transitive(M):
    """Returns True if the relation M is transitive, False otherwise."""
    return False
\end{lstlisting}

\subsection*{Warshall algorithm}

\begin{lstlisting}
def warshall(M):
    """Returns the transitive closure of the relation M (see page 606)."""

    # Reminder: be careful not to modify M!  I suggest that you use the 
    # deepcopy function provided in the Python copy module. 

    # Hint: Python boolean operators behave as you would want them 
    # to on 0's and 1's.  For example:
    # &gt;&gt;&gt; 0 or 1
    # 1
    return M

if __name__ == "__main__":

    # The following five matrices correspond to the relations from the
    # first question on the in-class exercises from 3/5.

    M1 = [[0, 0, 0, 0],
          [0, 1, 1, 1],    
          [0, 1, 1, 1],    
          [0, 0, 0, 0]]

    M2 = [[1, 1, 0, 0],
          [1, 1, 0, 0],    
          [0, 0, 1, 0],    
          [0, 0, 0, 1]]

    M3 = [[0, 0, 0, 0],
          [0, 0, 0, 1],    
          [0, 0, 0, 0],    
          [0, 1, 0, 0]]

    M4 = [[0, 1, 0, 0],
          [0, 0, 1, 0],    
          [0, 0, 0, 1],    
          [0, 0, 0, 0]]

    M5 = [[1, 0, 0, 0],
          [0, 1, 0, 0],    
          [0, 0, 1, 0],    
          [0, 0, 0, 1]]

    # Example 7 p. 602
    M7 = [[1, 0, 1],
         [0, 1, 0],    
         [1, 1, 0]]

    # Test reflexive, symmetric and transitive
    print reflexive(M1), '\t', symmetric(M1), '\t', transitive(M1)
    print reflexive(M2), '\t', symmetric(M2), '\t', transitive(M2)
    print reflexive(M3), '\t', symmetric(M3), '\t', transitive(M3)
    print reflexive(M4), '\t', symmetric(M4), '\t', transitive(M4)
    print reflexive(M5), '\t', symmetric(M5), '\t', transitive(M5)

    # Test Warshall's algorithm
    print 
    W = warshall(M7)
    print "M7", M7
    print "M7*", W

\end{lstlisting}


\section*{Section 9.3 (page 596)}

\subsection*{Exercise 2: a, b}
\textit{Your answer to this question should be formatted as python code that instantiates appropriate matrices as lists of lists:}

\begin{lstlisting}
Ma = ...
Mb = ...
\end{lstlisting}

\subsection*{Exercise 14: a, b, c}

\subsection*{Exercise 24}

\section*{Section 9.4 (page 606)}

\subsection*{Exercises 4, 8}

\subsection*{Exercise 20: a, b, c}

\end{document}

</pre></body></html>