Dynamic Programming

Question 1

Algorithm using Trusted Bird and Friend:
Step 1:

Answer 1

Question for the bird: Ask little bird whether or not this optimal solution contains the nth item from the large instance

Question 2

Algorithm using Trusted Bird and Friend:
Step 2:

Answer 2

Possible Answers from bird: There are K = n possible answers,
eg. K = 2; Yes and no.

Question 3

Algorithm using Trusted Bird and Friend:
Step 2.1

Answer 3

If little bird says nth item doesnt belong
No:
- Construct sub-instance: Delete nth item from consideration, giving us a smaller instance,
subI(no) = (V,(fsf) … (vn-1, pn-1))

• Constructing solution for my instance: Trusting both the bird and friend, my sol and costs are same as his.

Question 4

Algorithm using Trusted Bird and Friend:
Step 2.2:

Answer 4

If little bird says nth item belongs:
Yes:
- Constructing sub-instance: If nth item belongs, add it to OptSol(knapsack). V - vn.
We determine how to best fill rest of the remaining solution by asking our friend to solve the smaller instance SubI(no).

• Constructing solution for my instance: Trusting bird and friend, sol is same as friends, except i add nth item in OptSol / V
• Cost of sol: Having the extra item, my cost is pn more than the friends.

Question 5

Algorithm using Trusted Bird and Friend:
Step 2.3

Answer 5

If little bird is wrong:
- Const sub inst: if nth item doesnt fit, vn > V, we tell her shes wrong.
- Cost: Set the value of the nth item to -infinity to ensure it is not selected as best.

Question 6

Recursive Back Tracing Algorithm:
2 steps

Answer 6

Best of the best: Trust friend bc he is a recursive version of myself, not actually having a little bird, try all her answers and take the best of the best. (OMG JUST CLICKED, THIS BUILDS THE OptSubI that is too large bc of all the combination/subinstance we create using the little bird answers).

Base Cases: If there are n = 0 items, or volume of knapsack = 0, then only sol is put nothing in for price of 0.

Question 7

Dynamic Programming Alg
Step 1:

Answer 7

The set of Subinstances: SubI
Describe: By tracing the recursive alg we see that the set of subinstances given to me is V’ belongs [0..V],
and ‘i’ belongs [0…n]

Question 8

Dynamic Programming Alg
Step 3:

Answer 8

• Construct a table indexed by Subinstances:
  The table indexed by the set of subinstances will have a dimension for each of the parameters i and V’ used to specify a particular subinstance. The tables will be optCost[0..V, 0..n], and birdAdvice[0..V, 0..n]

Question 9

Dynamic Programming Alg
Step 4:

Answer 9

• Order in which to fill the table:
  Friends solve subinstances in an order so that no one has to wait. This could be one row at a time with both i and V’ increasing, one col at a time, or even diagonally.

Question 10

Dynamic Programming Alg Code Sections
1st step

Answer 10

% Table : subI[V’, i] is too large, so we do table [0.. V, 0 .. n] birdAdvice, optCost

Question 11

Dynamic Programming Alg Code Sections
2nd step

Answer 11

% Base cases: Base cases are when # of objs is 0. For each, solution is the empty knapsack with cost 0.
optSol = empty, optCost = 0, birdAdvice = empty

Question 12

Dynamic Programming Alg Code Sections
3rd step

Answer 12

% General cases: Loop over subinstances in table
loop i = 1 to n
loop V’ = 0 to V
Solve instance at this position and fill in the table here

Question 13

Dynamic Programming Alg Code Sections
4th step

Answer 13

% Try each possible bird answers.
% cases k = 1, 2 where 1=exclude 2=include
Define OptSol = optSol[V……
Define OptCost = optCost[V’,i-1]………………..
if V’ - vn > 0 then
% optSol(V’, i), 2) = optSol [V’ - vn, i-1] U i
optCost

else bird is wrong, set item empty, and cost -inf for that index

kmax = a k that maximized optCost
birdAdvice[] = kmax

Question 14

Dynamic Programming Alg Code Sections
Running Time

Answer 14

Number of subinstances in Table : T or V
number of bird answers is T * S or k
Running time is product of these O(V * k) or O(T^2 * S)