### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 578 Note 20 for CSE 565 at PSU

### View Full Document

## 35

## 0

## Popular in Course

## Popular in Department

This 43 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 35 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 578 Note 20 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 Dynamic Programming RNA Secondary Structure Allpairs shortest path LECTURE 20 3 3 Sofya Raskhodnikova SRaskhodnikova based on slides byE Demaine C Leiserson K Wayne 10102008 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 Shor Tes r PaThs Shor39TesT paTh problem Given a dir39ecTed graph G V E wiTh edge weighTs c find shor39TesT paTh from node 3 To node T VWl 39 allow nega rive weigh rs Ex Nodes r39epr39esenT agenTs in a financial seTTing and cVW is cosT of TransacTion in which we buy from agenT v and sell immediaTely To w 10 9 18 6 16 6 30 11 19 15 8 20 16 6 7 44 ShorTesT PaThs Failed A r remp rs DijksTr39a Can fail if There are negaTive edge cosTs Shor Tes r PaThs NegaTive CosT Cycles NegaTive cosT cycle ObservaTion If some paTh from 3 To T conTains a negaTive cosT cycle There does noT exisT a shor39TesT sT paTh oTher39wise There exisTs one Thcn is simple CW lt O Shor39TesT PaThs Dynamic Programming Def OPTi v engTh of shor39TesT vT paTh P using aT mosT i edges 00 if no such paTh exisTs Case 1 P uses aT mosT i1 edges OPTi v OPTi1v Case 2 P uses exacTIy i edges if v w is firsT edge Then OPT uses v w and Then seecTs besT wT paTh using aT mosT i1 edges 0 or 00 ifi0 OPTi v min OPTi l V min OPTi l Wva OtherWise vwEE Remark By pr39evious obser39vaTion if no negaTive cycles Then OPTnl v engTh of shor39TesT vT paTh ShorTesT PaThs Implemen ra rion Shortest PathG t foreach node v E V MO v w MO t 0 for i 1 to n l foreach node v E V Mi v t Mi l v foreach edge v w E E Mi v min Mi v Mi 1 w cmv Analysis mn Time nz space Finding The shor39TesT paThs MainTain a quotsuccessorquot for each Table enTr39y ShorTesT PaThs ImprovemenTs MainTain only one array Mv lengTh of shorTesT vT paTh found so far No need To check edges of The form v w unless Mw changed in previous iTeraTion Theorem ThroughouT The algoriThm Mv is lengTh of some vT paTh and afTer i rounds of updaTes The value Mv is no larger Than The lengTh of shorTesT vT paTh using s i edges Overall impacT Memory Om n Running Time Omn worsT case buT subsTanTially fasTer in pracTice BellmanFord EfficienT ImplemenTaTion Bellman Ford Shortest PathG s t foreach node v E V Mv co successorv Mt O for i 1 to n 1 foreach node w E V if Mw has been updated in previous iteration foreach node v such that v w E E if Mv gt Mw CW Mv lt Mw cw successorv w If no Mw value changed in iteration i stop The demonstration is for a sligtly different version ofthe algorithm see CLRS that computes distances from the sourse node ratherthan distances to the destination node 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Initialization 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Order of edge relaxation 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne End Ofpass 1 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne Example of BellmanFord 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne End of pass 2 and 3 and 4 10102008 SRaskhodnikova based on slides by E Demaine C Leiserson K Wayne DisTance VecTor ProTocol CommunicaTion neTwork Nodes z rouTers Edges z direcT communicaTion links I Cosf of edge z delay on lt na rurally nonnega rive bu r BellmanFord used anyway DijksTra39s algoriThm Requires global informaTion of neTwork BellmanFord Uses only local knowledge of neighboring nodes SynchronizaTion We don39T expecT rouTers To run in locksTep The order in which each foreach loop execuTes in noT imporTanT Moreover algoriThm sTill converges even if updaTes are asynchronous DisTance Vec ror39 Pr o rocol DisTance vecTor39 pr39oTocol Each r39ouTer39 mainTains a vecTor39 of shor39TesT paTh lengThs To every oTher39 node disTances and The firsT hop on each paTh dir39ecTions AlgoriThm each r39ouTer39 performs n separ39aTe compuTaTions one for each poTenTial desTinaTion node quotRouTing by r39umor39quot Ex RIP Xer39ox XNS RIP Novell39s IPX RIP Cisco39s IGRP DEC39s DNA Phase IV AppIeTalk39s RTMP CaveaT Edge cosTs may change during algor39iThm or39 fail compleTely 1 Cs 1 quotquot 1 quot39 quotcoun ring ro infini ryquot 2 1 I dele red PaTh VecTor ProTocols Link sTaTe r39ouTing no r Jus r The dis rance and firs r hop Each r39ouTer39 also sTor39es The enTir39e paTh Based on DijksTr39a39s algoriThm Avoids quotcounTingToinfiniTyquot problem and r39elcn ed difficulTies Requires significanle mor39e sTor39age Ex Bor39der39 GaTeway Pr39oTocol BGP Open ShorTesT PaTh Fir39sT OSPF DeTecTing NegaTive Cycles Lemma If OPTnv OPTn1v for a v Then no negaTive cycles are connecTed To T Pf BellmanFord algoriThm Lemma If OPTnv lt OPTn1v for some node v Then any shorTesT paTh from v To T conTains a cycle W Moreover W has negaTive cosT Pf by conTradicTion Since OPTnv lt OPTn1v we know P has exachy n edges By pigeonhole principle P musT conTain a direcTed cycle W DeleTing W yields a vT paTh wiTh lt n edges gt W has negaTive cosT cW lt O DeTecTing NegaTive Cycles Theorem Can deTecT negaTive cosT cycle in Omn Time Add new node T and connecT all nodes To T wiTh OcosT edge Check if OPTn v OPTnl v for all nodes v if yes Then no negaTive cycles if no Then exTr39acT cycle from shor39TesT paTh from v To T 0 O o o o 0 18f 5 45 11 De rec ring NegaTive Cycles ApplicaTion Currency conversion Given n currencies and exchange raTes beTween pairs of currencies is There an arbiTrage opporTuniTy Remark FasTesT algoriThm very valuable 8 17 F 800 310 43 23 2 350 110000 1 f 70 QM 56 De rec ring NegaTive Cycles Summary BellmanFord Omn Time Om n space Run BellmanFord for n iTeraTions instead of n1 Upon TerminaTion BellmanFord successor variables Trace a negaTive cycle if one exisTs See p 304 for improved version and early TerminaTion rule

### 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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "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.