The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
2.5k views

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
asked in Compiler Design by Active (3.7k points)
edited by | 2.5k views
+1

Code hoisting doesn't reduce time.

0
why s2 is false?

3 Answers

+11 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

answered by Active (3.5k points)
selected by
0
how did you arrive at this conditon
0
condition i+2=j  how comes
0
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 ?
+8 votes
answer - A

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

explaination:

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..
0
i did not take this case into consideration i'll edit the answer
0
Why S2 is false?
0
S2 has done simple code hoisting which compiler will do anyways to reuse the result
+7
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..
+3
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.
0
ok sir.. I'll keep that in mind.. thx..
+1
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];

a[i+2]=t2+1

return t2-3 and t2 is a[i+2] so where is the difference here ?
0
So the answer should be B.. isn't it @Arjun sir ??
0
So answer is B
0
hello how to do these kind of ques in exams as we can just check at what conditons the output will fail
0
ans is A or B please confirm?
0
@ana @himesh  @rohan

option A is correct .
0
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
answered by Active (4.8k points)
Answer:

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

44,490 questions
49,940 answers
165,704 comments
65,910 users