COSC 511   FA14   Quiz 10/23/2014

1. Consider these weighted intervals

            (1)
       |-----------|

                         (2)
                     |----------|

                                        (3)
                                     |------|

                                   (4)
                         |-----------------------|

Using dynamic programming:

1.a. Complete the array memo-ization array.



1.b. What is the optimum weight?



1.c. What is the subset of intervals that give maximum weight?


2. Consider these items and weights:
    w1  2
    w2  3
    w3  3
    w4  4
    
What is the subset of items that maximizes the sum of the weights and that 
sum is less than or equal to 9.

Using dynamic programs:

2.a. Complete the memo-ization array.



2.b. What is the optimum weight?



2.c. What is the subset of items that give maximum weight?