16. (5%) Consider the multiplication of four matrices with dimensions in the following order: 10x11,11x25,25x40,40x2. Find the optimal parenthesization of the above product and the minimum number of scalar multiplications needed.

18. Consider a set of 6 nodes 1, 2, 3, 4, 5, 6 and their corresponding weights: 2, 3, 4, 4, 5, 6.(a) (5%) Build a binary tree with these nodes appearing in the leaves such that the maximum of w[il x (1/2)^d[i] is minimized, where w[i] is the weight and d[i] is the depth of node i in the tree. Note that the root has depth 0. What is the optimal value?

16. (5%) Consider the multiplication of four matrices with dimensions in the following order: 10x11,11x25,25x40,40x2. Find the optimal parenthesization of the above product and the minimum number of scalar multiplications needed.

相關申論題

相關試卷