Logical Multiplication Algorithm

Question

This is my first stackoverflow question. I solved some exercises from Goodrich, Tamasia's Algorithm Design. However, I am completely unaware of this problem. Unusre where to start and how to act. Any advice would be appreciated. Here's the problem:

Boolean matrices are matrices such that each entry is 0 or 1, and matrix multiplication is performed using AND for * and OR for +. Suppose we are given two NxN random Boolean matrices A and B, so that the probability that any entry is either 1 is 1 / k. Show that if k is a constant, then there is an algorithm for multiplying A and B whose expected runtime is O (n ^ 2). What if k - n?

Answer 1

Matrix multiplication using the standard iterative approach is O (n ³ ) because you need to iterate over n rows and n columns, and for each element the vector is multiplied by one of the rows and one of the columns, which takes n multiplications and n-1 additions .

Psuedo code to multiply matrix a by matrix b and store in matrix c:

for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { int sum = 0; for(m = 0; m < n; m++) { sum += a[i][m] * b[m][j]; } c[i][j] = sum; } } 

For a Boolean matrix, as indicated in the task, AND is used in the place of multiplication and OR instead of adding, so it becomes this:

 for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { boolean value = false; for(m = 0; m < n; m++) { value ||= a[i][m] && b[m][j]; if(value) break; // early out } c[i][j] = value; } } 

It should be noted that after our logical “sum” is correct, we can stop calculating and exit the innermost loop, because ORing of any subsequent values ​​with true will generate true, so we can immediately know that the final result will be true.

For any constant k number of operations before we do it earlier (provided that the values ​​are random) will depend on k and will not increase with n. At each iteration, there will be a probability of (1 / k) ² that the cycle will end, because for this we need two 1s, and the probability that each record will be 1 is 1 / k. The number of iterations to completion will follow the geometric distribution , where p (1 / k) ² and the expected number of “samples” (iterations) to “success” (exit from the cycle) does not depend on n (except as the upper limit for the number of tests), therefore the innermost cycle runs in constant time (on average) for a given k, making up the general algorithm O (n ² ). The geometric distribution formula should give you some idea of ​​what happens if k = n. Note that in the formula given on Wikipedia, k is the number of trials.