2,211 views
1 votes
1 votes
A tridiagonal matrix [-2..2,5..9] is stored in row major order with base address 301.what is the address of data [0][8] if nonzero elements are stored??

1 Answer

4 votes
4 votes

Assumptions

  1. For the purpose of convenience, we name the tridiagonal array $A$.
  2. $BA$ is the Base Address of array $A$.
  3. Each element of the array occupies 1 unit space in memory. This assumption is reasonable as it is not specified in the question.
  4. $LA_{rows}$ and $LA_{cols}$ are lower bound indices of rows and columns respectively.
  5. $UA_{rows}$ and $UP_{cols}$ are upper bound indices of rows and columns respectively.
  6. $k$ is the count of the number of bytes each element of an array occupies in memory.

Here I will be presenting two ways to solve this problem, both equally good in this particular case. However, it is recommended to get familiar with the second method.

The Simple Way (Brute-force)

Mathematical Way (Rigorous)

Let us deduce a generalized formula for calculating the address of $A[i][j]$ out of observation from the standard tridiagonal matrix shown in above method.

  1. Each row of the two-dimensional tridiagonal array has 3 elements except for the first and the last row, which have 2 elements each. So if we have address of the first element of the array we can skip two elements completely, provided $i >1$
  2. Next, we are supposed to skip all the rows that come before $i^{th}$ row. This can be calculated by $(i-LA_{rows}-1)*3$
  3. Now we just need to skip either 0, 1, 2 elements at $i^{th}$ row because there are only 3 elements in each row. For this, we subtract the index of $j^{th}$ element by the number of zeroes preceding the first element in the $i^{th}$ row. At $i^{th}$ row there are $(i-LA_{rows}+1)-2$ zeroes. And there are $(j-LA_{cols})$ indexes before $(i,j)^{th}$ element. Thus we need to skip $(j-LA_{cols}) - ((i-LA_{rows}+1) - 2)$ elements.

Thus, we get the following generalized formula to calculate the address of A[i][j] provided $1<i<UA_{rows}$

$$Address(A[i][j]) = BA + k(2 + (i-LA_{rows}-1)*3 + (j-LA_{cols}) - ((i-LA_{rows}+1) - 2))$$

This expression can be simplified a bit, but I leave it as it is to avoid confusion among readers. I also leave the expression for calculating the address of $A[i][j]$ when $i = LA_{rows}$ or $i = UA_{rows}$ for readers as an exercise. It can be easily obtained by extending the idea discussed above.

So the answer to the question can be obtained by plugging in the values in the formula, since $-2<i<2$

$$Address(A[0][8]) = 301 + 1(2 + (0+2-1)*3 + (8-5) - ((0+2+1) - 2)) = 308$$

HTH

edited by

Related questions

0 votes
0 votes
1 answer
2
sandeep singh gaur asked Feb 18, 2019
1,131 views
A Sorted array of n elements contains 0 and 1 to find out majority of 0 and 1.How much time it will take???and please explain Meaning -majority of 0 and 1??
0 votes
0 votes
1 answer
3
SKR1997 asked Feb 17, 2019
858 views
Find the address of the position [10, 11, 12] of array A in column major order? Given Dimension is A[1:10, -5:15, -10:15], w is two word count, and Base address is 200.
0 votes
0 votes
0 answers
4