Question

Write pseudocode for Boolean product of two matrices.

Identify how sections of the code computing cycles grows with increasing matrix sizes.

10 points pseudocode

10 points description of code computing cycle growth

Answer 1

Part1

PSEUDOCODE FOR BOOLEAN PRODUCT OF TWO MATRICES:

I have added comments in the code for better understanding.

for(i = 0; i < n; i++)    //here we are using nested loops to multiply the two matrices
{
    for(j = 0; j < n; j++)
    {
        boolean status = false;    //initial bool status
        for(m = 0; m < n; m++)
        {
            status ||= a[i][m] && b[m][j];   //here we are using ||= to get the boolean value whether the multiplication turns true or not. if true then we have completed the multiplication.
            if(status)
                break; // if the value turns out to be true then break out of the loop
        }
        c[i][j] = status;   //final status value after the multiplication stored in the matrix
    }
}

Part 2

How the code computing cycles grows with increasing matrix sizes:

Description:

Boolean matrices are matrices where each entry is either 0 or 1, and matrix multiplication is performed by using AND for * and OR for +, hence for a boolean matrix, AND is used in place of multiplication and OR in place of addition. Now let us assume that we are given two matrices of the size n * n.

Let us say for any constant x inside the matrix, the number of operations before we can break out of the loop depends on x and will not increase with n, the size of the matrix. n may only decide the number of "trials" unitl "true" is obtained. At each iteration/trial there are (1/x)² chances that the loop will terminate by obtaining a true value, because we need two 1s and the chance of each entry being a 1 turns out to be 1/x. The number of trials before breaking or terminating will follow a Geometric distribution (GD) where p being the probability is (1/x)^2, so the innermost loop runs in constant time for a given k, making the overall algorithm O(n²).

When x is very large, you'll almost never exit early and your algorithm will be of the complexity O(n^3).

This describes the limiting behaviour of the algorithm.