Solutions to Problem Set #2

CS 155 -- October 11, 1999

  1. The table for m, and the table showing which value of k gives the optimal entry in the previous table, are
    0 1000 1500 2000 4500 5000
    - 0 1000 1500 3000 4500
    - - 0 2000 8000 6000
    - - - 0 3000 4000
    - - - - 0 3000
    - - - - - 0
    		 and
    - 1 1 1 1 1
    - - 2 3 4 5
    - - - 3 4 3
    - - - - 4 4
    - - - - - 5
    - - - - - -
    The resulting tree is thus: 
                               *
                         /   \
                       M1      *
                             /   \
                            *     M6
                          /   \
                         *     M5
                       /   \ 
                      *     M4
                     / \
                   M2   M3

  2. The algorithm can be identical to that used in Problem 1, with max replacing min. The tables corresponding to those of Problem 1 are
    0 1000 3000 5000 16000 19000
    - 0 1000 3000 12000 16000
    - - 0 2000 9000 15000
    - - - 0 3000 6000
    - - - - 0 3000
    - - - - - 0
    		 and
    - 1 2 2 2 5
    - - 2 2 2 2
    - - - 3 3 5
    - - - - 4 5
    - - - - - 5
    - - - - - -
    The resulting tree is thus: 
                               *
                         /   \
                       *       M6
                     /   \
                    *     *
                  /  \   /  \
                 M1  M2 M3  *   
                          /   \ 
                         M4   M5

  3. There are many examples. In one example, the sequence (di) = (10 100 10 9 8), so that the greedy algorithm would give the bracketing ((M1 x M2) x M3) x M4, which has a cost of 10000 + 900 + 720, or 11620. However the balanced tree has cost 10000 + 720 + 800, or 11520. This latter cost is optimal, since the other three trees have costs 720 + 8000 + 8000 = 16720, 9000 + 7200 + 8000 = 24200, and 9000 + 9000 + 720 = 18720.

  4. Tables for C and S, and for the value of r used for a given j and k are given in this order below.
    0 45 85 120 175 225
    - 0 25 50 95 135
    - - 0 15 45 80
    - - - 0 20 55
    - - - - 0 20
    - - - - - 0
    		 and
    5 45 60 70 85 100
    - 10 25 35 50 65
    - - 5 15 30 45
    - - - 5 20 35
    - - - - 5 20
    - - - - - 5
    		 and
    - 1 1 1 2 2
    - - 2 2 2 or 3 4
    - - - 3 4 4
    - - - - 4 4 or 5
    - - - - - 5
    - - - - - -
    The resulting tree is thus: 
                                P2
                          /    \
                        P1       P4
                       / \      /  \ 
                      Q0 Q1   P3    P5
                              /\    /\
                            Q2 Q3  Q4 Q5