retagged by
617 views
3 votes
3 votes
In an n x n C-matrix, all terms other than those in row 1, row n, and column 1 are zero. A C-matrix has at most 3n-2 nonzero terms. A C-matrix may be compactly stored in one-dimensional array by first storing row 1, then row n, and then the remaining column 1 elements. Calculate the location of an element A(i, j)?
retagged by

1 Answer

1 votes
1 votes

Let $f(i,j)$ be a function that takes $i,j$ ie column and row number and gives the index $k$ where $A(i,j)^{th}$ element is stored in the compact one-dimension array representation.

In the compact representation, first we’ll store elements of $row \space 1$ followed by $row \space n$ and at last remaining elements $column \space 1$.

Following this, we can define –

$\begin{align*} f(i,j) &= j, \text{ if } i = 1 \\  &= (n+j), \text{ if } i = n \\ &= (2n+(i-1)), \text{ if } i \neq 1,i \neq n \end{align*}$

Now, we’ve to merge these $3$ piecewise functions.

Now, what we want is few functions that can map to $0,1$ depending in the value of $i$.

  1. We want a function that can output $1$ when $i = 1$ and $0$ when $i \neq 1$.
  2. We want a function that can output $1$ when $i = n$ and $0$ when $i \neq n$.
  3. We want a function that can output $1$ when $i \neq 1, i \neq n$ and $0$ when $i = 1, i = n$.

We can do this using ceil and floor functions.

Consider this function,

$\begin{align*} \Bigl \lceil \frac{i-1}{i} \Bigr \rceil &=0, \text{ if } i = 1 \\ &= 1, \text{ if } i > 1 \end{align*}$

This is exactly opposite to what we need, so we can take its negation and add $1$ to make it behave as we want.

$\begin{align*} \left( 1 – \Bigl \lceil \frac{i-1}{i} \Bigr \rceil \right) &=1, \text{ if } i = 1 \\ &= 0, \text{ if } i > 1 \end{align*}$

Now, this is exactly what we need.

Consider this function,

$\begin{align*} \Bigl \lfloor \frac{i}{n} \Bigr \rfloor &=0, \text{ if } i < n \\ &= 1, \text{ if } i = n \end{align*}$

This is exactly what we need.

Using above equations, we can also fulfill our $3^{rd}$ function requirement.

$\begin{align*} \left( \Bigl \lceil \frac{i-1}{i} \Bigr \rceil \right) * \left( 1 – \Bigl \lfloor \frac{i}{n} \Bigr \rfloor \right) &=0, \text{ if } i = 1, i = n \\ &= 1, \text{ if } i \neq 1, i \neq n \end{align*}$

Now,

$f(i,j) = \left( 1 – \Bigl \lceil \frac{i-1}{i} \Bigr \rceil \right) * j + \left( \Bigl \lfloor \frac{i}{n} \Bigr \rfloor \right) * (n+j) + \left( \Bigl \lceil \frac{i-1}{i} \Bigr \rceil \right) * \left( 1 – \Bigl \lfloor \frac{i}{n} \Bigr \rfloor \right) * (2*n + (i-1))$

Now, we have $f(i,j)$ that gives index of $A(i,j)$. Assume that our $1-D$ array starts from base address $b$ and each element occupies $s$ bytes.

Location of $A(i,j) = b + \left( f(i,j) - 1 \right)* s$.

edited by

Related questions

0 votes
0 votes
2 answers
1
akama asked Sep 11, 2022
1,144 views
Explain the method to calculate the address of an element in an array. A 25*4 matrix arrayDATA is stored in memory in ‘row-major order’. If base address is 200 and 4 ...
0 votes
0 votes
2 answers
3
Arjun asked Oct 10, 2016
520 views
Consider the following declaration of a two dimensional array in C:char a[1000][40];Assuming that the main memory is byte addressable and that the array is stored startin...