Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 5 / e / Solution

Split a graph path of length at most $2k$ into two consecutive parts of length at most $k$, allowing a zero-length part. Conversely, concatenating two such parts gives a walk of length at most $2k$ and hence the same reachability. ThereforeStart at $P_1=I\vee E$, then square to obtain $P_2,P_4,P_8,\dots$. Stop at equality of successive matrices, or after the length bound reaches $n-1$. The invariant is now $P=P_{2^r}$ after $r$ squarings. Equality implies closure under composition, and the included identity matrix ensures reflexivity.

For the same elementary dense Boolean matrix multiplication and equality stopping test, the cost isThe additive constant covers the final stability check and the cases $m=0,1$. Thus, with $m\ge 2$, the number of cubic passes falls from $\Theta (m)$ to $\Theta (\log m)$. In terms of $n$ alone the worst-case bound improves from $\Theta (n^4)$ to $\Theta (n^3\log n)$ for these implementations. A directed chain also requires logarithmically many squarings. This comparison uses ordinary triple-loop multiplication, rather than a faster matrix multiplication method.