### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 690 Class Note for CSE 565 at PSU

### View Full Document

## 39

## 0

## Popular in Course

## Popular in Department

This 20 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 39 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 690 Class Note for CSE 565 at PSU

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Algorithm Design and Analysis LECTURE 19 Dynamic Programming Knapsack problem RNA Secondary Structure 39 a Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 1082008 Review questions ShortestpathGst shortest route from s to 2 LongestpathGst longest simple path from s to 2 Question Do Shortest Path and Longest Path have optimal substructure that can be used for a polytime dynamic programming algorithm What if the graph is a DAG 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 1 3f 539quot Knapsack Problem Given n objects and a quotknapsackquot Item i weighs wi gt O kilograms and has value vi gt O Knapsack has capacity of W kilograms Goal ll knapsack so as to maximize total value Ex 3 4 has value 40 W 11 0 Many packing problems t this model a 1 1 1 Assigning production jobs to factories Deciding which jobs to do on a single 2 6 2 processor with bounded time 3 18 5 Deciding which problems to do on an exam 4 22 6 5 28 397 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne w Knapsack Problem Given n objects and a quotknapsackquot Item i weighs wi gt O kilograms and has value vi gt O Knapsack has capacity of W kilograms Goal ll knapsack so as to maximize total value Ex 3 4 has value 40 W 11 Greedy repeatedly add item with n 1 1 maximum ratio v1 wt 6 Example 5 2 1 achieves only value 35 gt greedy not optimal 22 015me 2 18 5 6 397 28 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 7 1 Knapsack Problem Given n objects and a quotknapsackquot Item i weighs wi gt O kilograms and has value vi gt O Knapsack has capacity of W kilograms Goal ll knapsack so as to maximize total value Ex 3 4 has value 40 W 11 Greedy algorithm a 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 3313 I 35 Dynamic programming attempt 1 De nition OPTi maximum pro t subset of items 1 i Case 1 OPT does not select item i OPT selects best of l 2 il Case 2 OPT selects item i without knowing what other items were selected before i we don39t even know if we have enough room for i Conclusion Need more subproblems 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 33 Adding a new variable De nition OPTi W max pro t subset of items 1 iwith weight limit w Case 1 OPT does not select item i OPT selects best of l 2 il with weight limit w Case 2 OPT selects item i 0 new weight limit w wi OPT selects best of l 2 i l with new weight limit 0 if i0 0PTiw 0PTi lw if wigtw max0PTi 1w vi 0PTi 1w w otherwise 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Fi11 up an nbyW array Input n W wlp riv vh for W 0 to W MO w 0 for i 1 to n for w 1 to W if wi gt w Mi w Mi 1 w else Mi w max Mi l w vi Mi l w wiJ return Mn W 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne ltIgt 1 1 1 1 n 12 1 6 7 123 0 1 6 7 1234 o 1 6 7 12345 o 1 6 7 om243 value 22 18 2 40 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodn W O O O O O O O O O O O 1 1 1 1 1 1 1 1 7 7 7 7 7 7 7 7 19 24 25 25 25 25 7 1s 22 24 28 29 29 7 18 22 28 29 34 34 m 1 1 1 2 6 2 3 18 5 4 22 6 5 3928 7 332 How do we make turn this into 9 Dynamic programming and divide and conquer lends itself directly to induction Base cases OPTiOO OPTOWO no items Inductive step explaining the correctness of recursive formula 0 If the following values are correctly computed OPT0wlOPT1wl OPTnwl OPT0W OPTilw 0 Then the recursive formula computes OPTiw correctly Case 1 Case 2 from previous slide 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 3 About 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 machinereadable 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 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 1 5quot Time and Space Complexity Given n objects and a quotknapsackquot Item i weighs wi gt O kilograms and has value vi gt O Knapsack has capacity of W kilograms Goal ll knapsack so as to maximize total value W 11 What is the input size value weight In words 1 1 1 In bits 2 6 2 3 18 5 4 22 6 5 28 7 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 33 Time and space complexity Time and space n W Not polynomial in input size quotPseudopolynomial Decision version of Knapsack is NPcomplete KT chapter 8 Knapsack approximation algorithm There is a polytime algorithm that produces a solution with value Within 001 of optimum KT section 118 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne RNA Secondary STrucTure Problem RNA STring B blbzbn 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 EX 39 GUCGAUUGAGCGAAUGUAACAACGUGGCUACGGCGAGA A A A U o c l l CG U A A G I I I I G I I I U I A U U A I G A C G C U G I C G C G A GC I I G AU l G complemen rary base pairs AU CG RNA Secondary STrucTure Secondary sTrucTure A seT of pairs 5 bi bJ ThaT saTisfy WaTsonCrick S is a maTching and each pair in S is a WaTson Crick complemenT AU UA 66 or GC No sharp Turns The ends of each pair are separaTed by aT leasT 4 inTervening bases If bi bJ E S Then i ltj 4 Noncrossing If bi bJ and bk bl are Two pairs in S Then we cannoT have i lt k lt j lt l Free energy Usual hypoThesis is ThaT an RNA molecule will form The secondary sTrucTure wiTh The opTimum ToTal free energy approximaTe by number of base pairs Goal Given an RNA molecule B blbzbn find a secondary sTrucTure S ThaT maximizes The number of base pairs RNA Secondary S rr39uc rur39e Examples Examples 6 6 C U C G I AU U A basepair AUGUGGCCAU ok AUGGGGCAU lt s4 gt sharp rur39n AGUUGGCCAU crossing RNA Secondary S rruc rure Subproblems FirsT aTTempT OPTJ 2 maximum number of base pairs in a secondary sTrucTure of The subsTring blbzbJ maTch bar and bn DifficulTy ResulTs in Two subproblems Finding secondary sTrucTure in blbzb1 OW Finding secondary STPUCTUF C in b1b2bn1 lt need more subproblems Dynamic Programming Over InTervals NoTaTion OPTi J maximum number of base pairs in a secondary sTrucTure of The subsTring bibi1bj Base case If i zj 4 OPTi j O by nosharp Turns condiTion Case 1 Base bJ is noT involved in a pair OPTi j OPTiJ1 Case 2 Base bJ pairs wiTh br for some i s T ltj 4 noncrossing consTrainT decouples resuTing subproblems OPTi J 1 maxr OPTi T1 OPTT1 J1 Take max over T such ThaT i s T lt J4 and bT and bJ are WaTsonCrick complemenTs Bo r rom Up Dynamic Programming Over InTervals Q WhaT order To solve The subproblems A Do shorTesT inTervals firsT RNAb1bn Ignoring base cases 4 O O O for k 5 6 n 1 3 O O for i 1 2 n k i j i k 2 0 Compute Mi j 1 6 7 8 9 return Ml n using recurrence Time On3 Space 0n2 Exercise Find The secondary sTrucTure ThaT achieves The max value Dynamic Programming Summary Recipe Recursiver define value of opTimal soluTion CompuTe value of opTimal soluTion ConsTrucT opTimal soluTion from compuTed informaTion Dynamic programming Techniques Binary choice weighTed inTerval scheduling MulTiway choice segmenTed leasT squares KT secTion 63 Adding a new variable LCS knapsack Dynamic programming over inTervals RNA secondary sTrucTure parsing algori rhm for confexTfree grammar has similar sfrucfure Topdown memoizaTion vs boTTomup differenT people have differenT inTuiTions

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.