# Homework #11

Due in lecture, Thursday May 30June 6. Please do the homework in a workbook.

# From the Text

Complete the following questions from the text:

• Section 8.4: 22, 24
• Section 8.5: 2, 16, 46, 58, 60, 64
• Question 46: if not a partition, briefly say why.
• Question 58: You can expand the definition of “equivalence” to include any combination of rotations and reflexions. I think there 10 equivalence classes.
• Question 64: The wording is a little funny: start with a relation; take its transitive closure; take the reflexive closure of the result; take the symmetric closure of that result. Is the final result an equivalence relation? Hint: No. Come up with a counter-example.
• Section 8.6: 4, 12, 22(a,c), 34(a,b,c,d)

# Questions

1. Use the naïve algorithm (the $$\Theta(n^4)$$ one) to find the transitive closure of the relation represented by: $\mathbf{M}_R=\left[\begin{smallmatrix}0&1&0 \\ 1&0&1 \\ 0&0&0 \end{smallmatrix}\right]$
2. Use Warshall's Algorithm to find the transitive closure of the relation represented by: $\mathbf{M}_R=\left[\begin{smallmatrix}1&1&1 \\ 0&0&0 \\ 0&1&0 \end{smallmatrix}\right]$ Draw the graph of the relation represented by the matrix, and update it as you work through the algorithm.
3. Show that if $$(A_1,\preceq_1)$$ and $$(A_2,\preceq_2)$$ are total orders, then $$A_1\times A_2$$ is totally-ordered by lexicographic ordering. [We already know its a partial order. You only need to show that it's total.]