0 votes 0 votes b = b + c d = b + d b = b – d e = d + b The minimum number of nodes and edges present in the DAG representation of above basic block respectively are ? 4 and 5 5 and 4 6 and 6 6 and 7 Compiler Design compiler-design code-optimization directed-acyclic-graph made-easy-test-series + – balraj_allam asked Jan 27, 2019 balraj_allam 2.5k views answer comment Share Follow See all 43 Comments See all 43 43 Comments reply joshi_nitish commented Jan 16, 2018 reply Follow Share minimized DAG will have 3 nodes and 2 edges 0 votes 0 votes VS commented Jan 16, 2018 reply Follow Share @joshi_nitish Can you draw ? Please ! 0 votes 0 votes Pawan Kumar 2 commented Jan 17, 2018 reply Follow Share joshi_nitish, Sir can u plz share ur approach.... thanks 0 votes 0 votes Salazar commented Jan 17, 2018 reply Follow Share 3 nodes 4 edges ? 0 votes 0 votes Salazar commented Jan 17, 2018 i edited by Salazar Jan 17, 2018 reply Follow Share I think since the question says minimum we can apply number of algebraic operations and now im getting 3 nodes and 2 edges 0 votes 0 votes minal commented Jan 17, 2018 reply Follow Share i am getting e= b+c final expression ..yes 3 nodes 2 edge are correct ... 1 votes 1 votes minal commented Jan 17, 2018 reply Follow Share https://gateoverflow.in/2068/gate2014-3-34 1 votes 1 votes Pawan Kumar 2 commented Jan 17, 2018 reply Follow Share can u show the procedure sonam vyas mam 0 votes 0 votes minal commented Jan 17, 2018 reply Follow Share in given gate question someone comment in detail ... 0 votes 0 votes VS commented Jan 17, 2018 reply Follow Share @Salazar What are you doing ! This is absolutely wrong! b=b+c d=b+d b=b-d e=d+b You are taking d=e , this is not the case, See carefully , d= b + d = (b+c) +d e=d+b = d + b - d // Here, b=b+c and d=b+d e=b+d + b+c - (b+d) = b+c Now, d=b+c+d e=b+c They are not equal. PS: Here, the values of b or d are not the same as original , they are being modified in assignment statements. 0 votes 0 votes Salazar commented Jan 17, 2018 reply Follow Share Thanks @VS and @sonam could you also let me know when did you know to stop substitution to get the final expression ? It's kinda confusing 0 votes 0 votes Salazar commented Jan 17, 2018 reply Follow Share @vs here in below link some called shefali put this description is this wrong too ? just curious , im not getting correctly in https://gateoverflow.in/2068/gate2014-3-34 0 votes 0 votes Pawan Kumar 2 commented Jan 17, 2018 reply Follow Share @VS mam, in the given link the substitution in done in bottom to up order ... while you went from up to bottom .. doesn't it will affect the final expression 0 votes 0 votes minal commented Jan 17, 2018 reply Follow Share she did correct ..just simplify expression which will be minimum ... nothing else 0 votes 0 votes Pawan Kumar 2 commented Jan 17, 2018 i edited by Pawan Kumar 2 Jan 17, 2018 reply Follow Share VS Mam, Kindly see where did i go wrong... Thanks 0 votes 0 votes Salazar commented Jan 17, 2018 reply Follow Share @sonam could you please go through my solution as photo above and let me know if my approach is wrong, it's really confusing, i believe we can have different final expressions right also different minimal final expressions 0 votes 0 votes joshi_nitish commented Jan 17, 2018 reply Follow Share @Pawan your second last step is not correct, correct expression will be, $e=d+b=b+c+d-c-d=b$ $e=b$ 1 votes 1 votes Pawan Kumar 2 commented Jan 17, 2018 reply Follow Share joshi_nitish Sir, Thank u for correction.... so final expression would be e= b? 0 votes 0 votes joshi_nitish commented Jan 17, 2018 reply Follow Share @final expression will be, $e=b+c$ 0 votes 0 votes joshi_nitish commented Jan 17, 2018 reply Follow Share @pawan see this, $b=b+c$ $d=b+d\Rightarrow \color{Blue} d=b+c+d$ $b=b-d\Rightarrow b=(b+c)-(b+c+d)\Rightarrow\color{Blue} b=-d$ $e=d+b\Rightarrow e=(b+c+d)+(-d)\Rightarrow\color{Red} {e=b+c}$ $\color{Blue}{blue}$ marked are latest values 3 votes 3 votes Pawan Kumar 2 commented Jan 17, 2018 reply Follow Share joshi_nitish, Sir .... Thanks a ton 0 votes 0 votes Anu007 commented Jan 17, 2018 reply Follow Share b=b+c d=b+d d= b+c+d b=b-d b= (b+c)- (b+c+d) = - d e=d+b e= b+c+d - d = b+c 1 votes 1 votes VS commented Jan 17, 2018 reply Follow Share @Anu007 @joshi_nitish Final ans ? Min. #nodes and edges in DAG ? 0 votes 0 votes minal commented Jan 17, 2018 reply Follow Share 3 nodes 2 edges 0 votes 0 votes VS commented Jan 18, 2018 reply Follow Share @sonam vyas How ? 0 votes 0 votes joshi_nitish commented Jan 18, 2018 reply Follow Share because e=b+c will require only 3 nodes and 2 edges. 0 votes 0 votes srestha commented Jan 18, 2018 reply Follow Share @Sonam here at last we are getting b= -d and e=b+c both cannot be further minimized right? then it should be 4 nodes 3 edges isnot it?? 0 votes 0 votes minal commented Jan 18, 2018 reply Follow Share srestha see this 2 votes 2 votes bhuv commented Jan 18, 2018 reply Follow Share why don't we have nodes for e and = and their edges? 0 votes 0 votes VS commented Jan 18, 2018 reply Follow Share @sonam vyas @joshi_nitish b=b+c d=b+d d= b+c+d b=b-d b= (b+c)- (b+c+d) => b= - d e=d+b e= b+c+d - d => e=b+c In DAG shouldn't we should depict all the blue expressions above ? Why only the last one is being considered ? 0 votes 0 votes minal commented Jan 18, 2018 reply Follow Share yes only final expression 0 votes 0 votes VS commented Jan 18, 2018 reply Follow Share @sonam vyas Why ? 0 votes 0 votes minal commented Jan 18, 2018 reply Follow Share https://www.cse.iitm.ac.in/~krishna/cs3300/pm-lecture3.pdf hardly take 30 min ... will explain better than me 0 votes 0 votes VS commented Jan 20, 2018 reply Follow Share @sonam vyas I went through that pdf, still not clear to me, that why only final expression is considered? And If we think carefully , If we consider only e=b+c then where is variable 'd' gone ? 'd' is not an intermediate variable, it is given in starting itself ! b=b+c d=b+d d= b+c+d b=b-d b= (b+c)- (b+c+d) => b= - d e=d+b e= b+c+d - d => e=b+c 2 votes 2 votes MiNiPanda commented Jan 30, 2018 i edited by MiNiPanda Feb 1, 2018 reply Follow Share b1=b0+c0 d1=b1+d0 b2=b1-d1 e1=d1+b2=d1+(b1-d1) =b1 So, (b1,e1),b0,c0,d1,b2,d0 ---- 6 nodes 0 votes 0 votes kallu singh commented Jan 25, 2019 reply Follow Share 8 node and 10 edge 0 votes 0 votes Abhisek Tiwari 4 commented Jan 25, 2019 reply Follow Share @kallu singh Nope ans is 6 6 0 votes 0 votes Mk Utkarsh commented Jan 25, 2019 i edited by Mk Utkarsh Jan 25, 2019 reply Follow Share @Shubhanshu please verify 1 votes 1 votes Shubhanshu commented Jan 25, 2019 reply Follow Share @Mk Utkarsh I am getting 5 edges and 6 vertices. Here is my solution. 1 votes 1 votes Mk Utkarsh commented Jan 25, 2019 reply Follow Share Shubhanshu thanks (y) 0 votes 0 votes Shubhanshu commented Jan 25, 2019 reply Follow Share @Abhisek Tiwari 4 plz send the solution provided by them. 0 votes 0 votes Abhisek Tiwari 4 commented Jan 25, 2019 reply Follow Share Sol 0 votes 0 votes Shubhanshu commented Jan 27, 2019 reply Follow Share Refer - https://gateoverflow.in/299421/me_flt_cd#c299486 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes b = b + c d= b + d b= b - d e = d + b = d + b - d = b therefore, 6 nodes and 6 edges $ruthi answered Jan 30, 2018 $ruthi comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes by using first three equations make dag contains (6V,6E) and just reduce the last equation and get the final answer arun yadav answered Oct 9, 2020 arun yadav comment Share Follow See all 0 reply Please log in or register to add a comment.