Register

GO Classes DPP | COMPILER|EXPRESSION EVALUATION

233 views
1 1 vote

Consider the expression tree shown below. Each leaf represents a numerical value, which can be chosen from the set $\{-1,1\}$. Over all possible choices of the values at the leaves, what is the MAXIMUM possible value of the expressiog represented by the tree?

1 Answer

0 0 votes
  1. THE LEAVES (LEVEL 3) Each leaf can be either $-1$ or $1$.
     
  2. LEVEL 2 NODES (FROM LEFT TO RIGHT)
    • MULTIPLICATION NODE ($\times$): Possible values are $1 \times 1=1,(-1) \times(-1)=1$, or $1 \times (-1)=-1$.
       
      • Range: $\{-1,1\}$
         
    • DIVISION NODE ($÷$): Possible values are $1 / 1-1,(-1) /(-1)-1,1 /(-1)-1$, or $(-1) / 1--1$.
       
      • Range: $\{-1,1\}$
         
    • SUBTRACTION NODE ($-$): Possible values are $1-1=0,(-1)-(-1)=0,1$ -$(-1)=2$, or $(-1)-1=-2$.
       
      • Range: $\{-2,0,2\}$
         
    • MULTIPLICATION NODE ($\times$): Same logic as the first node.
       
      • Range: $\{-1,1\}$
         
  3. LEVEL 1 NODES
    • LEFT ADDITION NODE ($+$): Combines the first × node $\{-1,1\}$ and the ÷ node $\{-1,1\}$.
       
      • Maximum: $1+1=2$. Minimum: $-1+(-1)=-2$.
         
      • Range: $\{-2,0,2\}$
         
    • RIGHT MULTIPLICATION NODE ($\times$): Combines the - node $\{-2,0,2\}$ and the $x$ node $\{-1,1\}$.
       
      • Maximum: $2 \times 1=2$ or $-2 \times-1=2$.
         
      • Range: $\{-2,0,2\}$

         
    • THE ROOT NODE ($\times$) The root multiplies the results of the two Level 1 nodes. Both subtrees have a maximum possible value of $2$ and a minimum of $-2$.
       
      • To maximize the product: $2 \times 2=4$ or $(-2) \times(-2)=4$.
    Voting & Accepting an answer helps improve the community
    Answer:
    ← Previous · GO Classes DPP | PYT...Next → · GO Classes DPP | COM...
    ← Previous in category · GO Classes DPP | COM...Next in category → · GO Classes DPP | COM...
    Position:
    Show:

    Related questions

    1 1 vote
    2 2 answers
    251
    251 views
    GO Classes asked Jan 23
    251 views
    GO Classes DPP | COMPILER|DAG
    In a compiler's optimization phase, a Directed Acyclic Graph (DAG) is often used instead of a standard syntax tree to represent expressions. Consider the expression: $a=(...
    0 0 votes
    1 1 answer
    279
    279 views
    GO Classes asked Jan 23
    279 views
    GO Classes DPP | COMPILER|SYNTAX TREE
    Consider a syntax tree for the expression $a+b * c-d / e$. If the expression is evaluated using a post-order traversal of this tree, and the values at the leaves are $a=2...
    1 1 vote
    1 1 answer
    256
    256 views
    GO Classes asked Jan 23
    256 views
    GO Classes DPP | COMPILER|CODE OPTIMIZATION
    Consider the following three-address code sequence used for a loop:i = 0 L1: t1 = i * 4 t2 = base + t1 val = load t2 i = i + 1 if i < 100 goto L1Which optimization techni...
    1 1 vote
    1 1 answer
    252
    252 views
    GO Classes asked Jan 23
    252 views
    GO Classes DPP | COMPILER|LR(1) PARSER
    An $\mathrm{LR(1)}$ parser is being constructed for a grammar. If a particular state in the corresponding $\mathrm{LR}(1)$ canonical collection contains the item $[A \rig...