Question $5.$

$($a$)$ Suppose R is relation on set X where $|$X$|=$n$.$ Briefly explain

how we can associate an adjacency matrix M$\_($R$)$ of size n x n to R$.$

$(2$ marks$)$

$($b$)$ Write pseudocode for an algorithm that, given an adjacency matrix M$\_($R$)$ of a relation R$,$ returns $\text{'}1\text{'}$ if R is symmetric and reflexive; and returns $\text{'}0\text{'}$ otherwise. Analyze the time complexity of your algorithm for the best and worst cases.

$($c$)$ Given an adjacency matrix M$\_($R$)$ of a relation R$,$ write pseudocode for an algorithm that checks whether R is transitive. Discuss the correctness of your code and analyze the times complexity of your algorithm.

$($d$)$ Write pseudocode that computes after M$^(2)$:$=$M$\_($R$)$xxM$\_($R$)$ execute

False if M$^(2)[$i$][$j$]=1$ but M$\_($R$)[$i$][$j$]=0$ for some i and j; otherwise

returns True. Analyze the times complexity of your algorithm.

$($e$)$ Compare your the complexity of your algorithms in $($c$)$ and $($d$).$ If we use Strassen algorithm for matrix multiplication, how would it impact the time complexity of $($d$)?$

$($f$)$ Based on your answers for the above items and assuming Strassen'

algorithm for matrix multiplication, write pseudocode that, given

an adjacency matrix M$\_($R$)$ return $1$ if R is an equivalence relation

and $0$ otherwise. Analyze the time complexity of your algorithm

for the best and worst cases.

$($g$)$ Use your code to execute all the equivalence relations on a set of size $4.$ Print or draw all the equivalence relations on a set of size $4$