GATE CSE 2014 | Set 3 | Question: 10

Question

Let $A$ be the square matrix of size $n \times n$. Consider the following pseudocode. What is the expected output?

C=100;
for i=1 to n do
    for j=1 to n do
    {
        Temp = A[i][j]+C;
        A[i][j] = A[j][i];
        A[j][i] = Temp -C;
    }
for i=1 to n do
    for j=1 to n do 
        output (A[i][j]);

• A. The matrix $A$ itself
• B. Transpose of the matrix $A$
• C. Adding $100$ to the upper diagonal elements and subtracting $100$ from lower diagonal elements of $A$
• D. None of the above

Comments

1. swap symmetric off-diagonal elements
2. Perform step $1$ for all elements one-after-another
3. We will get the same matrix

---

for i=1 to n do
    for j=1 to n do 
    {
        Temp = A[i][j]+C;  // we can rewrite as Temp-c = A[i][j];
        A[i][j] = A[j][i];
        A[j][i] = Temp -C;
    }

assume, temp= temp – C

because C is just a constant.

for i=1 to n do
    for j=1 to n do
    { //below 3 line is just doing swap
        Temp = A[i][j];
        A[i][j] = A[j][i];
        A[j][i] = Temp;
    }

Now see the j=1 and goes till n. It will gave same matrix.

---

Similar question asked in TIFR

https://gateoverflow.in/95299

---

Attention ! , don't do this mistake : taking a 2 x 2 matrix running only till a[1][2] and leaving , considering it as transpose , when a[2][1] is considered its again interchanged , so the matrix becomes same as it was

Answer 1

A.
In the computation of given pseudo code for each row and column of Matrix $A$, each upper triangular element will be interchanged by its mirror image in the lower triangular and after that the same lower triangular element will be again re-interchanged by its mirror image in the upper triangular, resulting the final computed Matrix $A$ same as input Matrix $A$.

Comments

@StoneHeart How swap part is correct?

I think swap part is not implement correctly , it swaps the matrix 2 times.

the correct code should be –

for i=1 to n do
    for j=i+1 to n do

 

---

it can also be

for i=1 to n do
    for j=i to n do

---

Note : Do not forget outer for loop.

Answer 2

Take a small matrix

1  2

3  4

now trace the iteration

i=1,j=1 //no change in matrix cz a[i,j]=a[j,i]

i=1,j=2 // resultant matrix

1  3

2 4

i=2,j=1 //resultant matrix

1  2

3 4

i=2,j=2 //no change in matrix cz a[i,j]=a[j,i]

we get the original matrix as it is So, Option A is Ans.

Comments

What is the need of C in d question??why don't v add?

---

perfect explanation

---

nice explaination

Answer 3

take a small matrix
[a b]

[c d]

it will give
[a c

b+100 d]
for first row iterated

[a b + 100 -100
c d]
for second row iterated.
hence answer A.

Comments

what is the significance of last for loop in the question?

---

To print the rows of the Matrix.

---

It given transpose of the matrix i dont get the answer A pls perform i=2 and j=1 it doesn't swap the elements

Answer 4

Ok so basically for such Questions just need to see operation and then loop

 

Observe :- 

 

Temp = A[ i ] [ j ] + C ;
      A [ i ] [ j ] = A [ j ] [ i ] ;
      A [ j ] [ i ] = Temp - C ;


This is nothing but standard transpose operation


which can also be remembered as :

Temp = A[ i ] [ j ] ;
      A [ i ] [ j ] = A [ j ] [ i ] ;
      A [ j ] [ i ] = Temp ;

 

Now next thing to do is to observe the loops carefully,

There are basically 3 Rules or 3 similar type loops 

other than this it is mostly unlikely to be asked in exam



Rule 1 :-

for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
      swap(A[i][j], A[j][i]);

Every pair is visited twice

Output = Original Matrix







Rule 2 :- 

for(i=1;i<=n;i++)
   for(j=i+1;j<=n;j++)
      swap(A[i][j], A[j][i]);


Only upper triangular part is visited.

Each pair is swapped exactly once.

Output :- Transpose

 

Rule 3 :- 

 

for(i=1;i<=n;i++)
   for(j=1;j<i;j++)
      swap(A[i][j], A[j][i]);

 

Only lower triangular part is visited.

Again, each pair is swapped exactly once.

Output :- Transpose
 

That's it And all set!