10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Adam Smith Algorithm Design and Analysis LECTURE 19 Dynamic Programming •Knapsack problem •RNA Secondary Structure10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Review questions • Shortest-path(G,s,t) = shortest route from s to t. • Longest-path(G,s,t) = longest simple path from s to t •Question: Do Shortest Path and Longest Path have optimal substructure that can be used for a poly-time dynamic programming algorithm? –What if the graph is a DAG?10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Knapsack Problem • Given n objects and a "knapsack." -Item i weighs wi > 0 kilograms and has value vi > 0. -Knapsack has capacity of W kilograms. -Goal: fill knapsack so as to maximize total value. • Ex: { 3, 4 } has value 40. •Many “packing” problems fit this model –Assigning production jobs to factories –Deciding which jobs to do on a single processor with bounded time –Deciding which problems to do on an exam 1 value 18 22 28 1 weight 5 6 6 2 7 # 1 3 4 5 2 W = 1110/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Knapsack Problem • Given n objects and a "knapsack." -Item i weighs wi > 0 kilograms and has value vi > 0. -Knapsack has capacity of W kilograms. -Goal: fill knapsack so as to maximize total value. • Ex: { 3, 4 } has value 40. 1 value 18 22 28 1 weight 5 6 6 2 7 # 1 3 4 5 2 W = 11 •Greedy: repeatedly add item with maximum ratio vi / wi •Example: { 5, 2, 1 } achieves only value = 35  greedy not optimal.10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Knapsack Problem • Given n objects and a "knapsack." -Item i weighs wi > 0 kilograms and has value vi > 0. -Knapsack has capacity of W kilograms. -Goal: fill knapsack so as to maximize total value. • Ex: { 3, 4 } has value 40. 1 value 18 22 28 1 weight 5 6 6 2 7 # 1 3 4 5 2 W = 11 •Greedy algorithm?10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Dynamic programming: attempt 1 •Definition: OPT(i) = maximum profit subset of items 1, …, i. –Case 1: OPT does not select item i. •OPT selects best of { 1, 2, …, i-1 } –Case 2: OPT selects item i. •without knowing what other items were selected before i, we don't even know if we have enough room for i •Conclusion. Need more sub-problems!10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Adding a new variable •Definition: OPT(i, w) = max profit subset of items 1, …, i with weight limit w. –Case 1: OPT does not select item i. •OPT selects best of { 1, 2, …, i-1 } with weight limit w –Case 2: OPT selects item i. •new weight limit = w – wi •OPT selects best of { 1, 2, …, i–1 } with new weight limit10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Bottom-up algorithm •Fill up an n-by-W array. Input: n, W, w1,…,wN, v1,…,vN for w = 0 to W M[0, w] = 0 for i = 1 to n for w = 1 to W if (wi > w) M[i, w] = M[i-1, w] else M[i, w] = max {M[i-1, w], vi + M[i-1, w-wi ]} return M[n, W]10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Knapsack table n 1 Value 18 22 28 1 Weight 5 6 6 2 7 Item 1 3 4 5 2  { 1, 2 } { 1, 2, 3 } { 1, 2, 3, 4 } { 1 } { 1, 2, 3, 4, 5 } 0 0 0 0 0 0 0 1 0 1 1 1 1 1 2 0 6 6 6 1 6 3 0 7 7 7 1 7 4 0 7 7 7 1 7 5 0 7 18 18 1 18 6 0 7 19 22 1 22 7 0 7 24 24 1 28 8 0 7 25 28 1 29 9 0 7 25 29 1 34 10 0 7 25 29 1 34 11 0 7 25 40 1 40 W W = 11 OPT: { 4, 3 } value = 22 + 18 = 40How do we make turn this into a proof of correctness? • Dynamic programming (and divide and conquer) lends itself directly to induction. – Base cases: OPT(i,0)=0, OPT(0,w)=0 (no items!). – Inductive step: explaining the correctness of recursive formula • If the following values are correctly computed: – OPT(0,w-1),OPT(1,w-1),…,OPT(n,w-1) –OPT(0,w),…,OPT(i-1,w) •Then the recursive formula computes OPT(i,w) correctly –Case 1: …, Case 2: … (from previous slide). 10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. WayneAbout proofs • Proof is a rigorous argument about a mathematical statement’s truth – Should convince you – Should not feel like a shot in the dark –What makes a proof “good enough” is social –(Truly rigorous, machine-readable proofs exist but are too painful for human use). •In real life, you have to check your own work –Ideal: all problems should have grades 100% or 15% 10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne10/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Time and Space Complexity • Given n objects and a "knapsack." -Item i weighs wi > 0 kilograms and has value vi > 0. -Knapsack has capacity of W kilograms. -Goal: fill knapsack so as to maximize total value. What is the input size? •In words? •In bits? 1 value 18 22 28 1 weight 5 6 6 2 7 # 1 3 4 5 2 W = 1110/8/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Time and space complexity •Time and space: (n W). –Not polynomial in input size! –"Pseudo-polynomial." –Decision version of Knapsack is NP-complete. [KT, chapter 8] •Knapsack approximation algorithm. There is a poly-time algorithm that produces a solution with value within 0.01% of optimum. [KT, section 11.8]RNA Secondary Structure Problem RNA. String B = b1b2…bn over alphabet { A, C, G, U }. Secondary structure. RNA tends to loop back and form base pairs with itself. This structure is essential for understanding behavior of molecule. G U C A G A A G C G A U G A U U A G A C A A C U G A G U C A U C G G G C C G Ex: GUCGAUUGAGCGAAUGUAACAACGUGGCUACGGCGAGA complementary base pairs: A-U, C-GRNA Secondary Structure Secondary structure. A set of pairs S = { (bi, bj) } that satisfy:  [Watson-Crick.] S is a matching and each pair in S is a …