Problem Set #2

CS 155 -- due October 11, 1999

Each problem is worth 10 points

Trace the dynamic programming algorithm for the chained matrix multiplication problem to find the most efficient way to multiply a chain of matrices of respective sizes 10x5, 5x20, 20x10, 10x10, 10x30, and 30x10.
Construct a dynamic programming algorithm for the chained matrix multiplication problem that finds the least efficient way to multiply a chain of matrices. Trace your algorithm on the instance above.
Consider the greedy algorithm for the chained matrix multiplication problem of size n that works by first performing the multiplication that correpsonds to the largest value of d_i, and continues by calling itself on the resulting problem of size n-1. So in the example of Problem 1, the values of d_i used would be first d₅=30, then d₂=20, then (say) d₃=10, then d₄=10, and finally d₁=5, giving M₁ x (((M₂ x M₃) x M₄) x (M₅ x M₆)).
Find a problem instance for which n=4, the optimal solution is a balanced tree, and the given algorithm fails to find the optimal solution.
As discussed briefly in class, an instance of the Optimal Binary Search Tree problem consists of an integer n, a sequence of n weights (p_i)_i=1ⁿ corresponding to probabilities of successful searches for data items (P_i)_i=1ⁿ, and another sequence (q_i)_i=0ⁿ corresponding to probabilities of unsuccessful searches corresponding to data intervals (Q_i)_i=1ⁿ.
The goal is to find the binary tree with the cheapest cost, where the cost is the sum from 1 to n of (1+l_i )*p_i, plus the sum from 0 to n of m_i*q_i , where l_i is the level of the item P_i and m_i the level of the external node corresponding to Q_i.
Let C_j,k be the cost of the cheapest binary search tree for the subproblem consisting of the data items (P_i)_i=j+1^k and data intervals (Q_i)_i=j^k, so that the cost of the optimal tree for the original instance is C_0,n. If r ranges over the set of possible roots of the binary search tree for the subproblem, then

C_j,k = S_j,k + min_j<=r<k {C_j,r + C_r+1,k}, where the term S_j,k accounts for the fact that one extra comparison is required to reach every node in the new tree. This means that S_j,k equals the sum from j+1 to k of p_i plus the sum from j to k of q_i. Note that the term S_j,k appears outside the braces, since it is independent of r.
Based on this recurrence (and appropriate initial conditions), find the cost of the optimal binary search tree for the instance where n=5, (p_i ) = (30 10 5 10 10), and (q_i) = (5 10 5 5 5 5). Also sketch the optimal tree.