Data Structures,Algorithms&Applications In c++ page-249 Q-34

Question

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)?

Comments

Yes, my bad, i thought they asked index. I'll edit.

---

@shishir__roy Also when we modify a function using other function like say 

t(x) = x+5

y(x) = 1

now say z(x) = t(x) * y(x)

the resultant is same as t(x) but writing t(x) = t(x)*y(x) is odd in mathematics point of view right

---

It depends on the use case, I'm sure if we went looking we'll find many such examples.

Answer 1

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$.

Comments

Woahhhh what an ans!!