$($a$)$ Describe Warshall's algorithm for the sequences of the matrices $W_k=[w_{ij}^{[k]}]$ with kin$\{1,2,$dots,$n\}$ in terms of pscudocode.

$($b$)$ Show that Warshall's algorithm requires $2n^3$ bits operations to compute $W_n=M_{R^{**}}$ from the input $W=M_R$

$($c$)$ Let $R$ be the relation defined on a set $A=\{a,b,c,d,e\}$ by

$R=\{(a,c),(b,d),(c,a),(d,b),(e,d)\}.$

Use Warshall's algorithm to find the transitive closures of $R.$

$($d$)[$Extra$-$Credits: All or None$]$ Suppose that the boolean matrix $W_k=[w_{ij}^{(k)}]$ has $1$ in its $(i,j)-$th position if and only if there is a path from $v_i$ to $v_j$ with interior vertices from the set $\{v_1,v_2,$dots,$v_k\}.$ Show that

$w_{ij}^{[k]}=w_{ij}^{[k-1]}vv(w_{ik}^{[k-1]}{?}^{{?}^{?}}{w}_{kj}^{[k-1]})$

where $i,j,$ and $k$ are positive integers not exceeding $n.$