The Gateway to Computer Science Excellence
+14 votes

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

  1. S1 is false and S2 is false
  2. S1 is false and S2 is true
  3. S1 is true and S2 is false
  4. S1 is true and S2 is true
in Compiler Design by Active (3.3k points)
edited by | 3.4k views

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

3 Answers

+14 votes
Best answer

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

by Active (3.6k points)
selected by
how did you arrive at this conditon
condition i+2=j  how comes
Can anybody please explain what does " transformations " mean in S2.

Is it talking about changing the code of work1 and then comapring with work2 ?

And how do we actually compare their running time ?
i+2=j, how this condition taken?
i+2=j, how this condition is taken?
+8 votes
answer - A

when j == i+2 programs will return different results
by Loyal (8.6k points)
No.. it's answer is (A)..


if (i + 2) == j

then, a[j], in work1 is modifying.. that means (a[i + 2]) is modified.. so it's returning minus three with the modified value..

but in work2, it is saving a[i + 2] in some variable, then modifying a[j], and doing minus 3 with unmodified value.. So for this program state output won't be same.. so S1 is false..

therefore (A) is correct.. both are false..
i did not take this case into consideration i'll edit the answer
Why S2 is false?
S2 has done simple code hoisting which compiler will do anyways to reuse the result
S2 is false because, it is given high level language.. and this is not assembly language.. and compiler is sitting between them... So it is undecidable what corresponding assembly language the compiler will generate.. We don't know what optimization option will be used for compiling.. compiler may be smart enough, he may use dirty write concept to optimize the code.. So if we say it will ALWAYS improve the performance, we can not say it just by looking the high level language.. , isn't it?.. So so S2 is false..
Yes, in an actual system compiler can do anything. But in the question it says about transformations and hence we can assume a dumb compiler which straight away maps the given code to assembly code.
ok sir.. I'll keep that in mind.. thx..
when j=i+2 then

work1 will be

int x=a[i+2];

a[i+2]=x+1; return a[i+2]-3;

And work2 will be

int t1=i+2;

int t2=a[t1];


return t2-3 and t2 is a[i+2] so where is the difference here ?
So the answer should be B.. isn't it @Arjun sir ??
So answer is B
hello how to do these kind of ques in exams as we can just check at what conditons the output will fail
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.
–1 vote
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
by Active (4.7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,461 answers
100,240 users