ISI2017-PCB-CS-4

Question

A file $F$ holds the non-zero elements of two large $n \times n$ matrices, $a$ and $B$. The matrix entries are sorted as triplets $(i, j, \text{value})$, where $\text{value}$ is the $(i,j)$th element of a matrix. The file first stores the element of $A$ and then those of $B$. The matrix elements are stored in $F$ in an arbitrary order. In each matrix, only the elements

$$\begin{array}{c}(i,i):=i=1, \dots ,n\}, \\ \{(j,j+1):j=1, \dots ,n-1\} \text{ and } \\ \{(j+1, j); j=1, \dots ,n-1\} \end{array}$$

are non-zero. You are to add $A$ and $B$ and store the sum in $C$ and then print $A$, $B$ and $C$. Due to limited memory, for storing all three matrices, you can use space to hold only up to $9n$ values (NOT triplets). Is it possible to have a $O(n)$ solution? If no, give reasons. If yes, provide a solution. Clearly explain the data structure and how you are going to store, retrieve, and add the elements.

Comments

anyone ??

---

@Ashwin Kulkarni  @ joshi_nitish  @ Rishabh Gupta

---

aare koi th bolo ....

Answer 1

Only the non-zero elements are stored in the file. So, there are only (6n -4) triplets.

So, accessing any triplet would take O(n) time.

Since it is given in the question that the main memory can store 9n values.

So, we construct 9 arrays.

i) A₁ of size n-1

where A1 will store first n-1 values of the triplets (j,j+1,value)

A1 [j] = value of the triplet (j,j+1,value).

ii) B1 of size n-1.

Where B1 will store the next n-1 values of the triplets (j,j+1,value)

B1 [j] = value of the triplet (j,j+1,value)

iii) C1 of size n-1

where C1 [j] = A1 [j] + B1 [j]

iv) A2 of size n

where A2 will store first n values of the triplets (j,j,value)

A2 [j] = value of the triplet (j,j,value)

v) B2 of size n

where B2 will store next n values of the triplets (j,j,value)

B2 [j] = value of the triplet (j,j,value)

vi) C2 of size n

where C2 [j] = A2 [j] + B2 [j]

vii) A3 of size n-1

where A3 will store first n-1 values of the triplets (j+1,j,value)

A3 [j] = value of the triplet (j+1,j,value)

viii) B3 of size n

where B3 will store next n values of the triplets (j+1,j,value)

B3 [j] = value of the triplet (j+1,j,value)

ix) C3 of size n

where C3 [j] = A3 [j] + B3 [j]

Now, we are told to print the matrices A and B. This can be done by scanning through the file F and print the values of first (3n-2) triplets in the corresponding places in the matrix A and print the values of the next (3n-2) triplets in the corresponding places in the matrix B.

Rest elements of A and B are printed 0.

And for printing C we know,

(j,j+1)th element of C = C1 [j]

(j,j)th element of C = C2 [j]

(j+1,j)th element of C = C3[j]

And rest of the elements of C are printed as 0..

So, the data structure used in my solution is array.

and the time complexity is O(n).