GATE CS 2014 Set 3 Q34 — Local Optimization

To find the minimum number of nodes and edges in the Directed Acyclic Graph (DAG) representation, we construct the DAG step-by-step while applying algebraic simplifications:

1. Initial Leaves: We start with three leaf nodes for the initial values of the variables: $b$, $c$, and $d$.
   Total Nodes = 3, Edges = 0
2. a = b + c: Create Node 1 (operator +) with children $b$ and $c$. Label this node as $a$.
   Total Nodes = 4, Edges = 2
3. c = a + d: Create Node 2 (operator +) with children Node 1 ($a$) and $d$. Label this node as $c$.
   Total Nodes = 5, Edges = 4
4. d = b + c: Create Node 3 (operator +) with children $b$ and Node 2 ($c$). Label this node as $d$.
   Total Nodes = 6, Edges = 6
5. e = d - b: Since $d = b + c$ (from Node 3), substituting this gives $e = (b + c) - b = c$. Thus, $e$ is algebraically equivalent to the value at Node 2. No new node is created; we simply add the label $e$ to Node 2.
6. a = e + b: Since $e$ is equivalent to Node 2 (which represents $c$), we have $a = c + b = b + c$. This is algebraically equivalent to Node 1. No new node is created; we simply move the label $a$ to Node 1.

Thus, the final DAG contains exactly 6 nodes (3 leaves and 3 interior operator nodes) and 6 edges.