search
Log In
2 votes
218 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$.
in Algorithms 218 views

1 Answer

0 votes
//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);
}
0
you are pushing 31 elements to stack? :P

Related questions

1 vote
1 answer
1
176 views
Let $x, y$ be two non-negative integers $< 2^{32}$. By $x \wedge y$ we mean the integer represented by the bitwise logical $AND$ of the 32- bit binary representations of $x$ and $y$. For example, if $x = 13$ and $y = 6$, then $x \wedge y$ ... of the pseudo-code for the input $x = 13$? What will be the output of the pseudo-code for an arbitrary non-negative integer $x < 2^{32}$?
asked May 30, 2016 in Algorithms jothee 176 views
1 vote
1 answer
2
98 views
Let $A$ be a $30 \times 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. Show that there is a k such that $1 \leq k \leq 30$, $r_k \geq 17$ and there is an $l$ such that $1 \leq l \leq 40$, $m_l \leq 12$.
asked May 31, 2016 in Numerical Ability jothee 98 views
1 vote
0 answers
3
104 views
Let $x=(x_1, x_2, \dots x_n) \in \{0,1\}^n$ By $H(x)$ we mean the number of 1's in $(x_1, x_2, \dots x_n)$. Prove that $H(x) = \frac{1}{2} (n-\Sigma^n_{i=1} (-1)^{x_i})$.
asked May 30, 2016 in Numerical Ability jothee 104 views
1 vote
1 answer
4
177 views
Let $A$ and $B$ be two arrays, each containing $n$ distinct integers. Each of them is sorted in increasing order. Let $C = A \cup B$. Design an algorithm for computing the median of $C$ as efficiently as you can.
asked May 31, 2016 in Algorithms jothee 177 views
...