New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Algorithm Design and Analysis

by: Jacey Olson

Algorithm Design and Analysis CSE 202

Jacey Olson

GPA 3.69


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Computer Science and Engineering

This 8 page Class Notes was uploaded by Jacey Olson on Thursday October 22, 2015. The Class Notes belongs to CSE 202 at University of California - San Diego taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/226796/cse-202-university-of-california-san-diego in Computer Science and Engineering at University of California - San Diego.

Popular in Computer Science and Engineering


Reviews for Algorithm Design and Analysis


Report this Material


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: 10/22/15
CSE 202 Algori rhms Dynamic Programming 102902 CSE 202 Dynamic Programming UCSD Chess Endgames Ken Thompson Bell Labs solved all chess endgame posifions with s 5 pieces 1986 Some surprises KQ bea rs KZB Since 1634 believed To be draw 50 moves wi rhou r a pawn move or cap rure is no r sufficien r To ensure i r39s a draw By now mos r all 6piece endgames are solved foo Searching all possible games with 5 pieces going forward 50 or so moves is infeasible Today If Typical posifion has 4 moves search is 2100 long 2100 245 opssecond x 225 secondsyear x 1 billion years There is a beffer way CSE 202 Dynamic Programming Retrograde Analysisquot Insight there aren39t so many differenfpositions With 5 specific pieces there are s 645 positions 645 is about 109 large but quite feasible Make memory location for each position Position includes whose move it is Store count of possible moves for Black moves Initialize work list to all won positions for white For each win P in list process all positions Q that can move 39l39O P unless Q was already known to win for white If Q is a white move mark Q as win and add it to list If Q is a black move decrease possible move count by 1 If count 0 mark Q as win for white and put it on list 3 CSE 202 Dynamic Programming Why did this reduce work Can evaluate game tree by divide Si conuer Wmforwhiiep let Q1 Qk be all possible moves from P Wi Win for39WhlleQi Divide Combine if P is a white move and any WiT then return T if P is a black move and a WiT then return T return F Inefficient due to overlapping subproblems Many subproblems share the same subsubproblems 4 CSE 202 Dynamic Programming Dynamic Proqramminq Motto It39s not dynamic and it39s not programmingquot For a problem with optimal substructure property Means that like DampC you can build solution to bigger problem from solutions to subproblems and overlapping subproblems which makes DampC inefficient D namic Pro rammin builds a big table and fills it in from small subproblems to large More overhead but Another approach Is memOIzatIon k maybe more mtuutive Start wuth the big subproblems Store answers in table as you compute them Before starting on subproblem check if you39ve already done it CSE 202 Dynamic Programming Example Lonqest Common Substrinq Z z1 z2 2k is a substring of X x1 x2 xn if you can get Z by dropping letters of X Example Hello world is a substring of Helpl I39m lostwithout our langroverquot LCS problem given strings X and Y find the length of the longest Z that is a substring of both or perhaps find that Z CSE 202 Dynamic Programming LCS has opTimal subsTrucTurequot Suppose engThX x and engThYy LeT Xazb mean The aTh To bTh characTer of X ObservaTion If Z is a subsTring of X and Y Then The 3903 characTer of Z is The asT characTer of boTh X an Y so LCXY LC X1x1 Y1y1 I I Xx or of jusT X so LCXY LCSX Y1y1 or of jusT Y so LCXY LCX1x1 Y or neiTher so LCXY LCX1x1 Y1y1 7 CSE 202 Dynamic Programming Dynamic Programming for LCS Table Lij lengTh of LCS X1i Y1j If The lasT characTer of boTh X and is The same LCSX LCSX1x1 Y1y1 II Xx oTherwise LCSXY LCSX Y1y1 or LCSX LCSX1x1 V or LCSXY LCSX1x1 Y1y1 Tes us LOAD mGXLi1J391 XiyiLiJ391Li1J Each Table enTry is compuTed from 3 earier enTries 8 CSE 202 Dynamic Programming Dynamic Programming for LCS HELLOWORLD oo oooooo oo Looo 11111 11 A00011111111 mnhN0001111111 1 incremenoooo11111 11 2 R00011 11 222 000011 E2 2222 vooo11222222 E00111222 222 R00111223 33 9 CSE 202 Dynamic Programm ng But there are other substructures Work out the following at board Can we have Ti LCSX1i Y1i 9 How about the first half of X matches up with some part of Y and the rest with the rest Suggests LCSX maximum for i1y of LCSX1x2 Y1i LCSXx21xi1y We can make the table 1D instead onD 10 CSE 202 Dynamic Programming Summary For a good dynamic programming agori rhm Table should be lowdimensional keeps memory requiremen rs low Each Table entry should be fast To calculate keeps complexiTy low May decompose problems differenle Than a good Divide amp Conquer algori rhm 11 CSE 202 Dynamic Programming How To ge r your name on an algori rhm Use Dynamic Programming Earley39s algori rhm Parse a sTring using a CFG Vi rerbi39s agori rhm Break sTring info codewords Smi rhWa rerman algori rhm Match up Two sTrings of DNA or proTein FondWarshall Allpai rs shorTesT pa39rhs 12 CSE 202 Dynamic Programming Protein or DNA String Matching Biological sequences A proteins is a string of amino acids 20 charactersquot DNA is a string of base pairs 4 charactersquot Databases of known sequences SDSC handles the Protein Data Base PDB Human Genome 3x109 base pairs computed in 3901 String matching problem Given a query string find similar strings in database SmithWaterman algorithm is most accurate method FastA and BLAST are faster approximations CSE 202 Dynamic Programming SmithWaterman Algorithm Like LCS but more sophisticated Each pair xy of characters has affinity Axy easy to handle add affinity instead of Skipping characters incurs a penalty co k c1 penalty for skipping over k characters 4 4 4 6 lt using AR TS ED IOUS 2c11 M Y C R O A R E L I C 5 3 5 5 5 5 5 5 5 5 2 ScoreSO 292l M I C R O A R E L I S P A L L M 3 5 3 CSE 202 Dynamic Programming SmiThWaTer39man AlgoriThm We could handle skips by SWiJ max 0 SWi1J1 AXii kmlarx SWi Jk co clk kmlarxi SWik J co clk kgggi mgag SWikJm 2co C1km This would Take On4 Time ForTunaTely The lasT Term The doublemax is redundanT 12 M M1 w s Aquot1 wfj 502 hf a 5ng W ism jll l wimpva WT lo Elihu j wlmll and linen 2o glazing EliminaTing iT reduces The complexiTy To On3 15 CSE 202 Dynamic Programming SmiThWaTer39man in On2 Time AT cell ij of Table keep Thr39ee number39s sij score of besT maTching of X1i and Yij Tij besT score of X1i and Yij ThaT skips Xi uij besT score of X1i and Yij ThaT skips Yj AT each cell compuTe Sm new gap comm old gap Tij max si1 jcoc1 Ti1jc1 uij max si j1coc1 uij1c1 sij max si1j1Axiyj Tij uij 0 16 CSE 202 Dynamic Programming


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Amaris Trozzo George Washington University

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

Steve Martinelli UC Los Angeles

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

Parker Thompson 500 Startups

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

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.