4) Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: en
umerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer
1 answer:
Answer:
Running RECURSIVE-MATRIX-CHAIN is asymptotically more efficient than enumerating all the ways of parenthesizing the product and computing the number of multiplications of each.
the running time complexity of enumerating all the ways of parenthesizing the product is n*P(n) while in case of RECURSIVE-MATRIX-CHAIN, all the internal nodes are run on all the internal nodes of the tree and it will also create overhead.
Explanation:
You might be interested in
Answer:
The new root will be 2.
<em></em>
Explanation:
The binary tree is not properly presented (See attachment)
To answer this; first, we need to order the nodes of the tree in a pre-order traversal.
We use pre-order because the question says if something is removed from the left child.
So, the nodes in pre-order form is: 14, 2, 1, 5, 4, 16.
The root of the binary tree is 14 and if 14 is removed, the next is 2.
<em>Hence, the new root will be 2.</em>
