Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250

Quiz #15 ANSWERS

Wednesday, Dec. 8, 2004

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

1. [12 pnts.] Use Matrix Multiplication to find all of the 2 step paths if the following matrix represents all of the one step paths. Then answer the following questions about it.
   
   $$\left[\begin{array}{c c c c} 1 1 0 1\\ 1 1 0 1\\ 0 1 1 0\\ 1 0 1 1\\ \end{array}\right]$$
   
   
   1. What is the matrix that represents the 2 step paths?
      
      $$\left[\begin{array}{c c c c} 1 1 1 1\\ 1 1 1 1\\ 1 1 1 1\\ 1 1 1 1\\ \end{array}\right]$$
      
      

   2. Does this matrix also represent the transitive closure of the relation? ANSWER:Yes because it is complete
2. [10 pnts.] Compare and Contrast the two properties Symmetric and AntiSymmetric. Compare (state at least one similarity):
   
   
   One of the following:
   • They are both universal statements so not opposites of each other.
   • Both can have any values on the main diagonal.
   • Both will allow 0-0 in corresponding positions across the main diagonal.
   
   
   
   Contrast (state at least one difference): One of the following:
   • symmetric will allow 1-1 pairs across the main diagonal while antisymmetric will not.
   • Antisymmetric will allow 0-1 pairs across the main diagonal while symmetric will not.
3. [8 pnts.] Find the Closure indicated of each of the following relations that are over the set $\{1,2,3,4\}$.
   1. What needs to be added to this set to get the reflexive closure of R
      where R = $\{(1,1),(1,2),(2,1),(3,3)\}$? ANSWER: $\{(2,2),(4,4)\}$
      
      
      
      
      
      
      
   2. What needs to be added to this set to get the symmetric closure of S
      where S = $\{(1,1),(1,2),(2,1),(3,1),(2,4),(4,1),(4,3)\}$? ANSWER: $\{(1,3),(1,4),(3,4),(4,2)\}$
      
      
      
      
      
      
      
   3. What needs to be added to this set to get the symmetric closure of T
      where T = $\{(1,1),(1,3),(3,2),(4,3),(3,1),(2,3),(4,4),(2,2)\}$ ANSWER: $\{(3,4,)\}$

Web Accessibility