158 views
Let $A$ be a 30 × 40 matrix having 500 non-zero entries. For $1 \leq i \leq 30$, let $r_i$ be the number of non-zero entries in the $i$-th row, and for $1 \leq j \leq 40$, let $m_j$ be the number of non-zero entries in the $j$-th column.

Suppose that it is desired to create a stack of size 30 containing the values $r_1,\dots, r_{30}$, not necessarily in order such that the top of the stack contains the value $max_{1\leq i \leq 30} r_i$. Write pseudo-code for creating such a stack using a single scan of the matrix $A$.
| 158 views

//We have our matrix A and a stack "Stk" of size 30.
//A[i][j] refers to the entry at ith row and jth column of the given matrix A.
//Push(A, x) is a function that pushes x onto the stack A.

PROCEDURE(A)
{
int max = 0; //Stores temporary max(r[i]'s) during the scanning process.
int r[30]; //Stores number of non zero entries per row of matrix A.
int i, j; //Counter varibales.
for i = 1 to 30
{
r[i] = 0;
for j = 1 to 40
{
if (A[i][j] != 0)
{
r[i] = r[i] + 1;
}

}
if (r[i] > max)
{
Push(Stk, max);
max = r[i];
}
else
{
Push(Stk, r[i]);
}

}
Push(Stk, max);
}
by Boss (14.3k points)
0
you are pushing 31 elements to stack? :P

+1 vote