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

Does the question asks to write a function in C to calculate location of element $(i,j)$ or a mathematical function for the same?

---

@shishir__roy i think this is mostly a programming question because 

1. We should return location of A(i,j) so why would we think its a mathematical question
2. in the answer u said (i,j) should map to 0 or 1 but that’s not true and no where in the question it is said that non zero items are 1 so why mapping them only 0 or 1
3. my argument for point 2 is u wrote f(i, j) = j, if i = 1 so u are assuming that f(i, j) will return index of A(i,j) in the compact array but in the later part of ur answer u said f on (i,j) will map to 1 or 0 this is where im not connecting the dots

---

I never said $f$ on $(i,j)$ maps to $0,1$.

What I said was our piecewise function changes according to value $1$ so to combine $f$ we need $help$ of some $extra$ functions that maps to $0,1$ depending on value of $i$.

Writing a function in C for this question is very trivial, and writing mathematical function for same looked very hard (earlier), that's why I commented. And many times Gate has already asked this type of questions.

1. 1994

2. 1998

In lectures, sir also took one question to find index of $A(i,j)$ of an upper triangular matrix's 1-D array representation.

---

@shishir__roy bro here u took three pieces of a function f(i,j) and dealing them individually right 

i misinterpreted my bad 😅

Now comming to the question they asked location right so index should be added with base address 

Also why do u want to merge these pieces 

u can simply write in normal way right and mathematically speaking the final result result should not be given by f(i,j) technically i guess because u are modifying f(i,j) using some other function say h(i,j) so the resultant function may give same output as f(i,j) but it should not be f(i,j)

---

They didn't ask location, they asked index.

And the whole point of my answer was that piecewise function is equivalent to that final $f(i,j)$.

Yes, I guess I did a lot of extra/unnecessary work to get answer as a single function. But I believe doing these type of exercises will make us better at solving MSQs.

And I dint get it, why you think even if $f(i,j)$ gives correct answer, it should not be the final answer??

---

@shishir__roy bro 

they asked the location of A(i,j) so doesn’t it mean base address should be added

---

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!!