recategorized by
27,907 views
75 votes
75 votes

In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size $n \times n$, non-zero elements, (i.e elements of lower triangle) of each row are stored one after another, starting from the first row, the index of the $(i, j)^{th}$ element of the lower triangular matrix in this new representation is:

  1. $i+j$
  2. $i+j-1$
  3. $(j-1)+\frac{i(i-1)}{2}$
  4. $i+\frac{j(j-1)}{2}$
recategorized by

11 Answers

1 votes
1 votes

Answer Would be C if you go by Default representation of Array and Matrix i.e  Array starts with index 0 and matrix starts with 1
Plz note that matrix A[0,0] representation is NOT actually representing MATRIX but it is representing value stored in ARRAY of MATRIX at location 1,1. 

1 votes
1 votes

For the single dimensional array we assume that Array indices are starting from Zero. This is always assumed by default. But for the lower triangular matrix , we will assume that array indices are starting from  One Because the question is indirectly telling us to assume that way in the line “starting from the first row, the index of (i,j)th element of ...”

Now assume a Lower triangular matrix as:

1  0  0

2  3  0

4  5  6

When the non zero elements are stored in the array, the array will be: [1 2 3 4 5 6]

Now consider the element 5 in the lower triangular matrix. For element 5 array index will be 4

For that element i=3 and j=2 in the lower triangular matrix. The only option which gives answer as 4 is Option C)

Similarly it can be verified for other elements too.

 

0 votes
0 votes
$\begin{bmatrix} (0,0)& (0,1)& (0,2)& (0,3)\\ (1,0)& (1,1)& (1,2)& (1,3)\\ (2,0)& (2,1)& (2,2)& (2,3)\\ (3,0)& (3,1)& (3,2)& (3,3) \end{bmatrix}$

 

1D array for lower triangular matrix : $\begin{bmatrix} (0,0) & (1,0) & (1,1) & (2,0) & (2,1) & (2,2) & (3,0) & (3,1) & (3,2) &(3,3) \end{bmatrix}$

 

Now check for options:

index=3 i.e. (2,0) doesn't satisfy option A (index=i+j)

index=0 i.e. (0,0) doesn't satisfy option B (index=i+j-1)

index=0 i.e. (0,0) doesn't satisfy option c (index=ij-1+i(i-1)/2)

index=2 i.e. (1,1) doesn't satisfy option B (index=i+j(j-1)/2)

 

i think no options are correct
Answer:

Related questions

29 votes
29 votes
6 answers
1
Kathleen asked Oct 5, 2014
4,887 views
An array $A$ contains $n$ integers in non-decreasing order, $A \leq A \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $...
35 votes
35 votes
4 answers
2
Kathleen asked Oct 4, 2014
22,917 views
Linked lists are not suitable data structures for which one of the following problems?Insertion sortBinary searchRadix sortPolynomial manipulation
33 votes
33 votes
6 answers
3
Kathleen asked Oct 4, 2014
33,090 views
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $\text{1, 2, 3, 4, 5}$ in that...