### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 674 Class Note for CSE 565 at PSU

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Department

This 11 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 20 views.

## Similar to Course at Penn State

## Reviews for 674 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

Algerithm Design and Analysis LECTURE 17 Dynamic Programming WIS recap Segmented Least Squares Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9242008 Weigh red In rerval Scheduling Weigh red in rer39val scheduling problem Job j starts at sj finishes at fj and has weight or39 value VJ Two jobs compa rible if They donquott over39lap Goal find maximum weight subset of mutually compa rible jobs a o 1 2 3 4 5 6 7 8 9 10 013m maX v1 OPTp OPTj1 Time Weigh red In rerval Scheduling Memoiza rion Memoiza rion S ror39e r39esul rs of each subproblem in a Table lookupasneeded Input n 1s f1 f V1V n In 139 Sort jobs by finish times so that f1 5 f2 5 s fn Compute pl p2 pn forj1ton Mj empty MO 0 global ar39r39ay M Compute Optj if Mj is empty Mj max wj M Compute Opt pj M Compute Optj 1 return Mj Equivalent olgori rhm Bo r romUp Bo r romup dynamic programming Unwind recursion Input n slms f1 f v1mv n n n Sort jobs by finish times so that f1 5 f2 5 s f 9 Compute p1 p2 pme hOWfast Iterative Compute Opt M0 0 for j 1 to n Mj maxvj Mpj Mj1 Total time sorting 0n On logn Weigh red In rer39val Scheduling Finding a Solu rion Q Dynamic programming algor39i rhms compu res optimal value What if we want The solu rion itself A Do some posTpr39ocessing Run M Compute Optn Run Find Solutionn Find Solutionj if j 0 output nothing else if vj Mpj gt Mj 1 print j Find Solutionpj else Find Solutionj 1 of recursive calls s n gt On 63 Segmented Leas r Squares 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 yl axi b2 i1 SoluTion Calculus gt min error is achieved when quotSixiyi Eix ElJG Eiyi 39a ixi a b 2 2 n ixi 2ixi n lt 0n time Segmented Least Squares Segmented least squares Points lie roughly on a sequence of several line segments Given n points in The plane x1 y1 x2 y2 xn yn with x1lt x2 lt lt X find a sequence of lines that minimizes fx Q What39s a reasonable choice for fx To balance accuracy and parsimony 1 number of lines goodness of t Note discontinuous functions permitted SegmenTed LeasT Squares SegmenTed easT squares PoinTs ie roughly on a sequence of several ine segmenTs Given n poinTs in The plane x1y1 x2y2 xn y wiTh x1lt x2 lt lt X find a sequence of lines ThaT minimizes The sum of The sums of The squared errors E in each segmenT The number of lines L Tradeoff funcTion E c L for some consTanT c gt 0 Age092 Dynamic Programming Mul riway Choice NoTaTion OPTJ39 minimum cosT for poim s p1pi1 pj ei J minimum sum of squares for poim s pipi1 pj To compute OPTj Last segment uses poim s pipi1 pJ for some i CosT ei j c OPTil 0 if j0 OPT min eij c0PTi 1 otherwise 15139s 10 Segmented Leas r Squares Algori rhm INPUT n p1mpN c Segmented Least Squares MO O for j 1 to n for i 1 to j compute the least square error eU for the segment pi pj for j 1 to n Mj minlsisj eij c Mi 1 return Mn Running Time 0013 can be improved to On2 by precomputing ei j s Bottleneck compu ring ei j for39 Onz pair39s On per39 pair39 using previous formula 11

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

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

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

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