### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 657 Class Note for CSE 565 at PSU

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 24 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 17 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 657 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 18 Dynamic Programming Segmented LS recap Longest Common Subsequence Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 1062008 SegmenTed LeasT Squares LeasT squares FoundaTional problem in sTaTisTic and numerical analysis Given n poinTs in The plane x1y1 x2y2 xn yn Find a line y ax b ThaT minimizes The sum of The squar39ed er39r39or39 SSE Egg axi b2 i1 SoluTion Calculus gt min error is achieved when quotSixiyi Eixi Eiyi Eiyi a ixi a 3 b 2 2 n ixi Eixi n lt On time SegmenTed LeasT Squares SegmenTed leasT squares PoinTs lie roughly on a sequence of several line segmenTs Given n poinTs in The plane x1y1 x2y2 xn yn wiTh x1lt x2 lt lt X find a sequence of lines ThaT minimizes E sum of The sums of The squared errors in all segmenTs L number of lines Tradeoff via objecTive funcTion E c L for some consTanT c gt 0 Note discontinuous functions permitted Age609 Dynamic Programming MulTiway Choice NoTaTion OPTJ minimum 031 for poinTs p1pi1 pj ei J minimum sum of squares for poinTs pipi1 pj To compuTe OPTJ LasT segmenT uses poinTs pi pm pj for some i Cost 2 ei j c OPTil 0 if j 0 0PT mm eij c 0PTz 1 otherwise 15139s Segmented Least Squares Algorithm INPUT n p1pN c I Segmented Least Squares MO O for j 1 to n for i 1 to j compute the least square error ei for the segment p1 p 3 j ij c Mi 1 return M n can be improved to On2 by precomputing various statistics Running Time On3 Bottleneck computing ei j for Onz pairs On per pair using previous formula Least Common Subsequence Aka sequence alignment edit distance 1062008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Longest Common Subsequence LCS Given two sequences x1 m and y1 n nd a longest subsequence common to them both CCaDD 66th699 x AB I BD Aquot B BCBA A LCSxy yzBDCAB 1062008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Longest Common Subsequence LCS Given two sequences x1 m and y1 n nd a longest subsequence common to them both CCaDD 66th699 x AB C BK D B BCAB I Lcsltxygt yzBDCABA 1062008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Motivation 0 Approximate string matching Levenshtein 1966 Search for occurance get results for occurrence Computational biology NeedlemanWunsch 1970 s Simple measure of genome similarity cgtacgtacgtacgtacgtacgtatcgtacgt acgtacgtacgtacgtacgtacgtacgtacgt 1062008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne I Motivation 0 Approximate string matching Levenshtein 1966 Search for occurance get results for occurrence Computational biology NeedlemanWunsch 1970 s Simple measure of genome similarity acgtacgtacgtacgtcgtacgtatcgtacgt aacgtacgtacgtacgtcgtacgta cgtacgt n lengthLCSxy is called the edit distance 1062008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Bruteforce LCS algorithm 1062008 Check every subsequence ofx1 m to see if it is also a subsequence ofy1 n Analysis 0 Checking 0n time per subsequence 2 subsequences of x each bitvector of length m determines a distinct subsequence ofx Worstcase running time 0072 quot exponential time A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 39 Dynamic programming algorithm Simpli cation 1 Look at the length of a longestcommon subsequence 2 Extend the algorithm to nd the LCS itself Notation Denote the length of a sequence 3 by s Strategy Consider pre xes of x and y De ne cij LCSx1 iy1 j 0 Then cm n LCSx y 1062008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne m 555 Recursive formulation Ci1j 11 ifxiyi CW maXci 1j cij 1 otherwise Base case ciJ0 if i0 or j0 Case xi yU The second case is similar 1062008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 233 o o Dynamlcprogrammlng Optimal substructure An optimal solution to a problem instance contains optimal solutions to subproblems If 2 LCSx y then any pre x ofz is an LCS of a pre x ofx and a pre x of y 1062008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Recursive algorithm for LCS LCSx y i j ignoring base cases ifxU yj then cij e LCSxy i 1j 1 1 else cij e maXLCSx y i 1j LCSx y ij 1 return ci j Worse case xi yj in which case the algorithm evaluates two subproblems each with only one parameter decremented 1062008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne WE 555 Recursion tree Height m n gt work potentially exponential 1062008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne W 555 Recursion tree m 7 n 6 Same subproblem n r j 7 A r l X l l 7 Qt xl39l 21 cl 24 99gt 7 g Height m n gt work potentially exponential but we re solving subproblems already solved 1062008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Dynamicprogramming Overlapping subproblems A recursive solution contains a small number of distinct subproblems repeated many times The number of distinct LCS subproblems for two strings of lengths m and n is only mn 1062008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Memoization algorithm Memoization After computing a solution to a subproblem store it in a table Subsequent calls check the table to avoid redoing work LCSx y ij if ci j NIL then ifxi y39 then cij e LCSx y i 1j 1 1 zme else cz 6 max LCSx 9401 1 before 9 LCSx9y9 la1 Time mn constant work per table entry Space mn 1062008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne IDEA A B C B D A B Computethe 0 0 0 0 0 0 0 0 table bottom up B 0 0 1 1 11 1 1 D 0 0 11 1 2 2 2 C 0 0 1 2 2 2 2 2 A 01 1 2 2 23 3 B 0 12 23 3 34 A 0 1 2 2 3 3 4 4 1062008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne IDEA A B C B D A B Compute the 0 0 0 0 0 0 0 0 table bottomup B 0 01 11 1 11 Time mquot D 0 0 1 1 12 2 2 C 0 0 1 2 2 2 2 2 A 01 1 2 2 23 3 B 0 12 23 3 34 A 0 1 2 2 3 3 4 4 1062008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne IDEA B C B A Compute the 0 0 0 0 0 0 0 0 table bottomup B 0 01 1 1 1 1 1 Time mquot 0 0 11 12 2 2 Reconstruct LCS by tracing C 00 1 2 2 22 2 backwards 0 1 1 22 2 3 3 B 0 1 2 2 3 3 3 4 A 0 1 2 2 3 3 4 4 1062008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne w U gt IDEA A Compute the table bottomup Time mn Reconstruct LCS by tracing backwards Multiple solutions are possible 1062008 AUJNNr dow wwNNr dr O WWNNNr O UJUJNNP O NNNr dr OO gtwgtOUw A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne IDEA w gt Compute the table bottomup B Time mn Reconstruct LCS by tracing backwards NNNr r OO Space mn B wwNNr r O KT book A Ominm n A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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