We discussed two algorithms for computing the transitive closure of a given relation. Use the pseudocode given below to complete the questions. Algorithm 0.1 (A Procedure for Computing the Transitive Closure). procedure transitive closure (MR : zeroone n × n matrix) A := MR B := A for i := 2 to n A := A ⊙ MR B := B ∨ A return B (the zero-one matrix for R∗ .) Algorithm 0.2 (Warshall Algorithm). procedure Warshall (MR : n × n zeroone matrix) W := MR for k := 1 to n for i := 1 to n for j := 1 to n wij := wij ∨ (wik ∧ wkj ) return W (W = [wij ] is the zero-one matrix for R∗ .) 1. In lecture, I mentioned that Warshall’s algorithm is more efficient, when compared to Algorithm 0.1, at computing the transitive closure. Verify this claim by doing the following. (a) (15 points) Write python scripts that will perform both algorithms. (b) (10 points) Once your scripts are working correctly, run a sequence of tests using random zero-one matrices with n = 10, 20, 30, ..., 100 where you record completion time and take a 10 run average for each. Plot your results on an appropriate graph. (c) (5 points) What conclusions can you claim based on your results from part (b)? 2. (20 points) Both algorithms given above can be adapted to find the reflexive closure of the transitive closure for a given relation. Adapt your scripts from 1.(a) so that you have the option to find either the transitive closure, or the reflexive transitive closure, for a given relation. Test your scripts, for each of the four cases, on a random 20 x 20 zero-one matrix and return the matrices resulting from given tests
We discussed two algorithms for computing the transitive closure of a given relation. Use the pseudocode given below to complete the questions.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
