recategorized by
27,908 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

8 votes
8 votes
An example of lower triangular matrix of size 3 x 3 is given below.
1   0   0
2   3   0
4   5   6
While storing we will store as 1 2 3 4 5 6.
Index of the  (i,j)th element = the number of elements in (i - 1) rows + j
                                          = (1 + 2 + ... + i-1) + j
                                          = [i(i-1)/2] + j
Hence option (c)
6 votes
6 votes

Although best answer contain all information but i want to demonstrate by example lets take one example of 3x3 lower triangular matrix

1 0 0
2 3 0
4 5 6

now above matrix is stored on following basis in new representation

1 2 3 4 5 6

Now to find index of (i,j)th element by assuming that both array representations are starting from 1.

now lets find the location of element (2,2) by all options

A) i+j = 2+2 = 4 (wrong)

B) i+j-1 = 2+2-1 =3 (right) but check for (3,1) and it will give the same answer so (wrong).

C) (j-1) + i(i-1)/2 = 1 + 2.1/2 =2 (wrong)

D) i + j(j-1)/2 = 2 + 2.1/2 =3 (right) check for (3,1) also it will give the same answer so (wrong).

So clearly no option is matching  either answer should be j + i(i-1)/2 or if new array representation will start from 0 then answer will be C.

 

 

2 votes
2 votes

Let Matrix indices are of form  1st row -->11 12 13 14....1n

                                                2nd row--> 21 22 23 23...2n,  

Therefore number of non zero elements present in row1 = 1, row 2 =2 , row3 =3 .....row i = i

Number of non zero elements before ith row = 1+2+3+.....i-1 =  i(i+1)/2

Now array starts from index 0. To store i(i+1)/2 elements in array, indexes used will be   {i(i+1)/2} -1 as array starts from 0th index.

Now, we have 'j' more elements to cross to reach(i,j), so the index of (i,j) will be {i(i+1)/2} -1 +j = {i(i+1)/2} +j-1

Therefore Answer is C

Answer:

Related questions

29 votes
29 votes
6 answers
1
Kathleen asked Oct 5, 2014
4,888 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,919 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,092 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...