Consider evaluating the following expression tree on a machine with load-store…
2011
Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables \(a, b, c, d,\) and \(e\) are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?
Answer: D. 3 — Key idea: use the Sethi–Ullman register-count rule. Each leaf requires 1 register. For a binary node, if the left and right subtrees require equal numbers of…
- A.
2
- B.
9
- C.
5
- D.
3
Attempted by 42 students.
Show answer & explanation
Correct answer: D
Key idea: use the Sethi–Ullman register-count rule. Each leaf requires 1 register. For a binary node, if the left and right subtrees require equal numbers of registers r, the node requires r+1; otherwise it requires the maximum of the two.
Leaves a, b, c, d, e: each requires 1 register.
(a - b): children need 1 and 1, so the node needs 2 registers.
(c + d): children need 1 and 1, so the node needs 2 registers.
(e - (c + d)): children need 1 (for e) and 2 (for (c + d)), so the node needs max(1,2) = 2 registers.
Root ( (a - b) + (e - (c + d)) ): left and right subtrees each need 2, so equal case => need 2 + 1 = 3 registers.
Conclusion: the minimum number of registers required to evaluate the expression without storing intermediates in memory is 3.