9.5k views

Consider the basic block given below.

a = b + c
c = a + d
d = b + c
e = d - b
a = e + b 

The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

1. $6$ and $6$
2. $8$ and $10$
3. $9$ and $12$
4. $4$ and $4$

edited | 9.5k views
0
Notice - No node no node for '=' operator
+18

...............................

0
THIS IS IN SYLLABUS?
0
Yeah it is in syllabus. Question can be asked from anywhere if it is even a little bit in syllabus. So leave recent out of syllabus topics carefully.

A normal DAG construction will give $8$ nodes and $10$ edges as shown below.

Since, this question asks for minimum possible, we can assume algebraic simplification is allowed. So, $d = b + c, e = d - b$; can be simplified to $d = b + c$; $e = c$; Similarly, $e = d - b$; $a = e + b$; can be simplified to $a = d$. This gives the following DAG with $6$ nodes and $6$ edges.

Correct Answer: $A$

by Veteran (434k points)
edited
+1
Why is definition d added to node a? In 3rd statement c is getting redefined and hence the new value of c would be used for defining d. Hence a new node for d is created. What am I missing, Arjun Sir?
0
Sorry. It was a mistake. I have corrected it now.
+2
sir. the lnk is dead i need to study DAG . plz provide a gud link .
0
thanx arjun sir
0
@Arjun Sir, The link here is not working,have any alternative?
+2
Is DAG in syllabus?  but can questions of this type be expected anyone reply.... Isn't DAG used for optimisation?
0
is this in syllabus???
0
yes. it's in syllabus.
0
@Arjun Sir

In 2nd Figure am unable to find edge of  e = d-b; except this am understand ...I think 7 edges will be there?plzz look if you have time?
0
but code optimization is not, then how is it in syllabus? :(
0
what sort of question can we expect with dag because it involves code optimization techniques which are nt in syllabus?
0
@sushmita

I think it is intermediate code and DAG combination question and both of them are in syllabus..
+4
can we do it like this-

a=b+c

c=a+d

d=b+c

e=d-b

a=e+b

Now d is common subexpression so we need not compute it again-

Hence it will become-

a=b+c

c=a+d

e=a-b

a=e+b=a-b+b=a -----> redundant

Finally it becomes-

a=b+c

c=a+d

e=a-b

It will also require 6 nodes and 6 edges.
+63

isn't it right?

0
It is also correct!!!
+12

...........

0
Where is the assingment operator?
0
Had minimum not been asked, would be then go with 8 and 10 option?
0
@prayas

It is not required  because in DAG x:=y type of assignments need not to be performed (not required) untill and unless it is used for computation of further expression.
0

@shefali1

@sushmita

will ​​​​​@shefali1 method will always give correct result??

because it seems bit easy draw  DAG from reverse.

Best approach of doing this question is "Go in reverse order". and it has asked for minimum so we can simplify wherever possible.

A = (E+B)

((D-B)+B) = (D) Because both + , - has same precedence

(B+C)

(B+(A+D))

(B+((B+C)+D))

by Active (4.5k points)
0

@Nitesh Singh 2

How you put the bracket?

0
Brackets are just to indicate "appropriate value has been substituted in place of the previous variable".

Simplifying the given equations :

d = b + c (given) e = d – b (given) => d = b + c and e = c

e = d - b (given) a = e + b (given) => a = d

Thus, the given DAG has 6 nodes and 6 edges.

by Boss (10k points)
option B
by Active (2.6k points)
by Loyal (8.6k points)