SI333 Quiz 2

1. Suppose that we ran our final memoized algorithm for matrix chain multiplictaion, augmented to keep track of the best "k" values, on matrices A0...A5 and, when it was over, the "bestK" table looked like this:

   _|_0__1__2__3__4__5_
   0|-1  0  1  1  2  2
   1|-1 -1  0  0  2  2 
   2|-1 -1 -1  1  3  3 
   3|-1 -1 -1 -1  3  4 
   4|-1 -1 -1 -1 -1  4 
   5|-1 -1 -1 -1 -1 -1 
   

   Give the optimum parenthesization discovered by the algorithm for: A₀ A₁ A₂ A₃ A₄ A₅

2. Suppose you had a list of numbers x1,x2,...,xn and you wanted to divide them into sets A and B such that the sum of the numbers in A and the sum of the numbers in B was as close as possible. I propose solving this problem with a greedy algorithm based on the following "greedy choice". Pick the largest number and put it into whichever of A and B has the lowest sum currently (place number randomly if A and B are tied). So, for example:

   X = [3 4 7 8] A = {}    B = {}
         Choose 8
   X = [3 4 7]   A = {8}   B = {}
         Choose 7
   X = [3 4]     A = {8}   B = {7}
         Choose 4
   X = [3]       A = {8}   B = {4,7}
         Choose 3
   X = [ ]       A = {8,3} B = {4,7}
   

   Prove that this greedy algorithm does not always yield the optimum solution.

3. Here's a different kind of Knapsack problem. In this version each object has a weight and a value and you want to fill the Knapsack without exceeding capacity so that the total value in the Knapsack is as great as possible. The Fractional Knapsack Problem is this same problem except that instead of a whole object being either in or out of the knapsack, you can put pieces in it. For example:

   Problem:
   Capacity C = 7
   Obj1=[weight=4,value=10], Obj2=[weight=5,value=2], Obj3=[weight=6,value=8]
   Solution: 100% Obj1, 0% Obj2, and 50% Obj3, which gives weight=7 and value=14

   So a precise formulation of the fractional knapsack problem is:

   Given:
   C, a positive integer, the capacity
   A, a list of n objects, where Obj_i has weight w_i and value v_i.
   Find: Percentages p₁,...,p_n such that p₁*v₁ + ... + p_n*v_n is as large as possible given the requirement that p₁*w₁ + ... + p_n*w_n ≤ C.

   Your task: Provide a greedy choice for this problem that always gives optimal solutions. You don't have to prove that it always gives optimal solutions, but explain how it would come up with the optimum solution to the example problem above.