1
$\begingroup$

Given an $n \times m$ matrix $A$ where

  • $m-n=1$
  • The value of any $A$[$i,j$] is either $1$ or $0$
  • If $A$[$i,j$] $=1$ then $i<j$

Does anyone know of an algorithm which would run as follows and what its complexity might be:

  1. Starting with the last column, column $m-1$, traverse each index $A[i,m-1]$ (where $0 \leq i < m-1$).
  2. Keep track of all $i$ such that $A[i, m-1] = 1$.
  3. Letting $S = \{i : A[i, m-1] = 1\}$, determine whether $A[j,k] =1$ for all $j,k\in S$ such that $j < k$.
  4. For each $A[j,k]=1$, add 1 to a counter.
  5. Repeat process for remaining columns $m-2, m-3,\ldots,2$ (no need to do this for column 1, as column 0 will be all 0s).
  6. Return count.

So for example if we have the following $5\times6$ array:

$$ \begin{array}{cccccc} 0& 1& 1& 0& 1& 0 \\ 0& 0& 1& 0& 1& 0 \\ 0& 0& 0& 0& 0& 1 \\ 0& 0& 0& 0& 1& 1 \\ 0& 0& 0& 0& 0& 1 \end{array} $$

Then we would start with column 5.

There is a value of $1$ at $A$[$2,5$], $A$[$3,5$] , and $A$[$4,5$], and so we would

  • Check if $A$[$2,3$] has a value of 1. If it does, add 1 to the counter. It doesn't.
  • Check if $A$[$2,4$] has a value of 1. If it does, add 1 to the counter. It doesn't.
  • Check if $A$[$3,4$] has a value of 1. If it does, add 1 to the counter. It does, increase counter.

Repeat this process for columns 4, 3, and 2, and then return the count.

$\endgroup$
  • 5
    $\begingroup$ I don't understand your question. You ask if there's an algorithm that "runs as follows", and then describe an algorithm. Doesn't that answer your question? (Hint: the answer would appear to be "yes".) $\endgroup$ – David Richerby Dec 12 '16 at 23:05
  • 1
    $\begingroup$ Wouldn't algorithm spell way to solve a problem? What is the problem, and does the procedure described solve it? $\endgroup$ – greybeard Dec 12 '16 at 23:11
  • $\begingroup$ @DavidRicherby yes you are right. I suppose I was looking for code to similar algorithms so I could get a feel as to how to most efficiently implement such an algorithm. For example, I'm not quite sure how to best achieve the desired count described above. What would be the best way to keep track of the $i$ values where $A$[$i,m$] $=1$ for some given column_m? And then check the various combinations (which meet the specified criteria) to see if there is a value of $1$ at that index? $\endgroup$ – Parry Dec 12 '16 at 23:49
  • 3
    $\begingroup$ If your actual question is "Can you find another algorithm that produces the same one as this?", please edit your post, and tell us what requirements the other algorithm must satisfy for you to consider it a satisfactory solution. Also, can you specify what the desired output is, in a simpler way (and one that doesn't just say "run the following algorithm")? That's a lot to read to understand what you're trying to accomplish. $\endgroup$ – D.W. Dec 12 '16 at 23:53
  • $\begingroup$ What does this algorithm do? Where did you find it? I think you could get helpful answers if you provide some more details. As far as I can see, it calculates a set $S$ of indices of the rows (where there is a 1) and gives the number of upper off-diagonals that are nonzero of the submatrix induced by $S$. Its worst-case complexity would be $O(mn^2)$. $\endgroup$ – Azzoubeir Dec 13 '16 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.