GATE CSE 2006 | Question: 55

Question

Consider these two functions and two statements S1 and S2 about them. 

int work1(int *a, int i, int j) { int x = a[i+2]; a[j] = x+1; return a[i+2] - 3; }

int work2(int *a, int i, int j) { int t1 = i+2; int t2 = a[t1]; a[j] = t2+1; return t2 - 3; }

S1: The transformation form work1 to work2 is valid, i.e., for any program state and input arguments, work2 will compute the same output and have the same effect on program state as work1 

S2: All the transformations applied to work1 to get work2 will always improve the performance (i.e reduce CPU time) of work2 compared to work1

• A. S1 is false and S2 is false
• B. S1 is false and S2 is true
• C. S1 is true and S2 is false
• D. S1 is true and S2 is true

Comments

Code hoisting doesn't reduce time.

---

why s2 is false?

---

important difference to notice in this question is

return a[i+2] - 3; in work1

return t2 - 3;     in work2

so in first one we are directly doing calculation on array value.

where as in second one we are storing value somewhere.

So there are chances that in first one value in array can get modified .

And now we have to find that combination for which it gets modified

 

---

Is this  question really out of syllabus now?? It is tagged to be out-of-sylllabus...

Answer 1

Consider an array a = 1 2 3 4 5 and condition i + 2 =j. Lets take i =0 and j =2 for this example.

Work 1, 

x = a[0+2] = 3

a[2] = 3 + 1 = 4;  which means a = 1 2 4 4 5

return a[0+2] - 3 = 4 -3 = 1

Work 2

t1 = 0 + 2 = 2

t2 = a[2] = 3

a[2] = 3 + 1 = 4, which means a = 1 2 4 4 5 again

return t2 - 3 = 3 -3 =0

Hence S1 is false when i + 2 =j. S2 will also be false, since we cant explicitly say the performance of work2 will always be better than work1.

Hence answer is A

Comments

i+2=j, how this condition is taken?

---

in the work2 , wer are storing value of a[t1] i..e a[i+2] in t2 and at the end we are returning t2 - 3 and in between the value of t2 is not changed. Now in work1 we are returning a[i+2] - 3 at the end, now in order for this value to be different from t2 - 3 we should somehow modify the value at a[i+2].

a[j] = x+1, now if j==i+2 that means a[i+2] is modified and the values will be different.

---

in work1, in line_2, we are changing the array, and then in line_3, we are again accessing the value and returning it.

 

In work2, we are storing a value of the array to a variable, then changing array, and then returning the stored value, that's where it changes, we, in work2 did not account for the change in the array that might affect the return value.

Answer 2

answer - A

when j == i+2 programs will return different results

Comments

ans is A or B please confirm?

---

@ana @himesh  @rohan

option A is correct .

---

May anyone pls tell how such questions can be solved during gate exam? As S1 is false only when j=I+2.How to check the code robustness for any condition? Any suggestions would be appreciated.

Answer 3

Ans- C

Only an extra variable t1 has been added in work 2 instead of directly computing the subscript as in work 1.The output will be same. S1 is true.

The addition of variables t1 and t2 will not improve the performance in anyway. i.e S2 is false.

Corrcet me I'm wrong