Due in lecture, Thursday ~~May 30~~June 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

- 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]\]
- 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.
- 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.]