### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 205 Note 16 for CSE 565 at PSU

### View Full Document

## 23

## 0

## Popular in Course

## Popular in Department

This 27 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 23 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 205 Note 16 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 16 Dynamic Programming 0 plus FFT Recap Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9242008 DiscreTe Fourier Transform CoefficienT To poinTvolue Given a polynomial o0 o1 x on1 xquot391 evoluoTe if of n disTincT poinTs x0 x I I n139 Key idea choose xk 2 00k where 1 is principal n rh roof of uniTy yo 1 1 1 1 1 a0 yl 1 n1 Dz 003 O Du 1 a1 yz 1 002 004 we I 00201 1 02 y3 1 m3 16 19 om 1 a3 yH 1 Dn l w2n 1 0301 1 wn 1n 1 ail 1 l l Discre re Fourier Transform Fourier ma rrix Fn FasT Fourier Transform Goal EvaluaTe a degree n1 polynomial Ax a0 an1 xquot391 aT iTs n rh roofs of uniTy 000 001 con1 Divide Break polynomial up inTo even and odd power39s Aevenx a0 azx a4x2 an22 xquot3912 Aodd x a1 a3x a5x2 an21x 3912 AX Aevenx2 X Aoddx2 Conquer EvaluaTe degr39ee Aevenx and Aoddx aT seT of all squares of nTh roofs of unity Combine O Aw Aevenvk 00k Aoddvk o s k lt n2 Aakquot2 A Vk 00k Aoddvk o s k lt n2 When n is even There are only n2 possible values of 00k CVCI I 00kn2 Dllt FFT AIgoriThm fft n aoa1 an1 if n 1 return a0 eoe1en21 lt FFTn2 aoa2a4an2 dod1dn21 lt FFTn2 a1a3a5an1 fork0ton2 1 wk e2ikn k yk lt ek1dk k Ykn2 ek 39 w dk return yo Y1 I I Yn1 FFT Summary Theorem FFT algorithm evaluates a degree n1 polynomial at each of the nh roots of unity in On log n steps assumes n is a power of 2 Running time T2n 2Tn On gt Tn On log n On log n F 0 1 a0a1anl A 0 a yO 3939san yn l lt coefficient pointvalue representation representation Poin rValue To CoefficienT RepresenTaTion Inverse DFT Goal Given The values yo yn1 of a degree n1 polynomial aT The n poinTs m0 m1 con1 find unique polynomial a0 a1 x an1xquot391ThaT has given values aT given poinTs a0 1 1 1 1 1 391 yo a1 1 D1 D2 D3 mn l M 2 1 Dz D4 006 um 1 yz a3 1 ws me 009 m Dam 1 y3 art 1 1 Dn l w2n 1 0 3n 1 I I wn 1n 1 ynl l l Inverse DFT Fourier ma rrix inverse Fn391 Inverse FFT Claim Inverse of Fourier maTrix is given by following formula 1 1 1 1 1 1 9 1 0392 00 3 o m39ln39l G l 1 0 2 4 m a m 2n 1 n n 1 w a 9 6 03 9 D 3n 1 1 w n l Dam 1 Dam 1 m n an l Consequence To compuTe inverse FFT apply same algoriThm buT use 003912 e 392 i quot as principal n39rh roof of uniTy and divide by n Polynomial MulTiplicaTion Theorem Can mulTiply Two degree n1 polynomials in On log n sfeps coefficien r r epr esen ra rion coefficien r r epr esen ra rion a0a1an1 c c c b0b1bn1 1 2 FFT On log n inver39Se FFT On log n AX0 I Ax2n1 poin rvalue mul riplica rion Bx0 Bx2n1 om CXoCx1Cx2n1 InTeger MulTiplicaTion InTeger mulTiplicaTion Given Two n biT inTegers a an1 a1aO and b bn1 blbo compuTe Their producT c a x b ConvoluTion algoriThm 1 Form Two polynomials Now a Am b 32 Bxb0b1xb2x2bn1xn 1 CompuTe Cx Ax x Bx EvaluaTe C2 a x b Running Time On log n complex ariThmeTic sTeps 2 n Ax a0 a1x a2x 0 an1x Theory Schb nhageSTrassen 1971 On log n log log n biT operaTions MarTin FUrer Penn STaTe 2007 On log n 239 9quot biT operaTions PracTice GNU MulTiple Precision AriThmeTic Library GMP proclaims To be quotThe fasTesT bignum library on The planeTquot IT uses bruTe force KaraTsuba and FFT depending on The size of n K 1 Wrapup Divide and Conquer 0 Look for recursive structure Steps Divide Break into smaller subproblems Conquer Solve subproblems Combine compute nal solution Often helps to compute extra information in subproblems eg inversions recursive call also sorts each piece If pieces independent get parallelization Chapter 5 Dynamic Programming Design Techniques So Far Greedy Build up a solution incrementally myopically optimizing some local criterion Divideandconquer Break up a problem into subproblems solve subproblems and combine solutions 0 Dynamic programming Break problem into overlapping subproblems and build up solutions to larger and larger subproblems 1082007 S Raskhodnikova based on slides by K Wayne Dynamic Programming H is rory Bellman 19503 Pioneered The sysTemaTic sTudy of dynamic programming ETymology Dynamic programming planning over Time SecreTary of Defense was hosTile To maThemaTical research Bellman soughT an impressive name To avoid confronTaTion quotiT39s impossible To u3e dynamic in a pejoraTive SenSequot quotsomeThing noT even a Congressman could objecT Toquot Reference Bellman R E Eye of fhe Hurricane AnAufobography Dynamic Programming ApplicaTions Areas BioinformaTics ConTroI Theory InformaTion Theory OperaTions research CompuTer science Theory graphics AI compilers sysTems Some famous dynamic programming algoriThms Unix diff for comparing Two files ViTerbi for hidden Markov models decoding convoluTionaI codes SmiThWaTerman for geneTic sequence alignmenT BellmanFord for shorTesT paTh rouTing in neTworks CockeKasamiYounger for parsing conTexT free grammars Fibonacci Sequence Sequence defined by a1 1 1 3 5 8 13 21 34 Running Time Review QuesTion Prove Thcn The soluTion To The recurrence TnTn1Tn2 81 is exponenTial in n CompuTing Fibonacci Sequence FasTer ObservaTion LoTs of redundancy The recursive algoriThm only solves n1 differenT subproblems MemoizaTion STore The values reTurned by recursive calls in a sub Table ResulTing AlgoriThm Linear Time In facT a lognTime algoriThm exisTs WeighTed In rer39val Scheduling WeighTed inTer39vaI scheduling problem Jobj sTar39Ts aT sj finishes aT fJ and has weighT or39 value VJ Two jobs compaTibIe if They don39T overlap Goal find maximum weighT subseT of muTuaIIy compaTibIe Jobs Time UnweighTed InTerval Scheduling Review Recall Greedy algoriThm works if all weighTs are 1 Consider jobs in ascending order of finish Time Add Job To subseT if if is compaTible wiTh previously chosen Jobs ObservaTion Greedy algoriThm can fail specTacularly if arbiTrary weighTs are allowed weigh r 999 weigh r 1 a Time WeighTed InTer val Scheduling Notation Label Jobs by finishing Time f1 s f2 s s 1 Def pJ largesT index i ltj such Thcn Job i is compaTible wiTh J Ex p8 5 p7 3 p2 O Dynamic Programming Binary Choice NoTaTion OPTJ value of opTimal soluTion To The problem consisTing of job requesTs 1 2 J Case 1 OPT selecTs Job j collecT profiT VJ can39T use incompatible Jobs pJ 1 pJ 2 1 musT include opTimal soluTion To problem consisTing of remaining compaTible jobs 1 2 pJ op rimal subs rruc rure Case 2 OPT does noT selecT Job J musT include opTimal soluTion To problem consisTing of remaining compaTible jobs 1 2 j1 o if j0 PT 39 0 J maxvj 0PTpj 0PTj 1 otherwise WeighTed InTerval Scheduling BruTe Force Br uTe force algoriThm Input n s1msn f1PNfn V1vn Sort jobs by finish times so that f1 5 f2 5 s fn Compute pl p2 pn Compute Optj if j 0 return 0 else return maxvj Compute Optpj Compute Optj 1 WeighTed InTerval Scheduling BruTe Force ObservaTion Recursive algoriThm fails specTacularly because of redundanT subproblems gt exponenTial algoriThms Ex Number of recursive calls for family of quotlayeredquot insTances grows like Fibonacci sequence V P0 0 P0 J2 WeighTed InTerval Scheduling MemoizaTion MemoizaTion STor39e resulTs of each subproblem in a Table lookupasneeded Input n s1msn f1PNfn V1vn Sort jobs by finish times so that f1 5 f2 5 s fn Compute pl p2 pn global army M Compute Optj if Mj is empty Mj maxwj M Compute Optpj M Compute Optj 1 return Mj WeighTed InTerval Scheduling Running Time Claim Memoized version of algoriThm Takes On log n Time SorT by finish Time On log n CompuTing p On log n via sorTing by sTarT Time M Compute Opt j each invocaTion Takes 01 Time and eiTher i reTurns an exisTing value M j ii fills in one new enTry Mj and makes Two recursive calls Progress measure I nonempTy enTries of M iniTially I O ThroughouT I s n ii increases 1 by 1 2 aT mosT 2n recursive calls Overall running Time of M Compute Opt 1391 is On Remark On if jobs are presorTed by sTarT and finish Times WeighTed InTer val Scheduling Finding a SoluTion Q Dynamic programming algor39iThms compuTes opTimal value WhaT if we mm The soluTion 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 2 On WeighTed InTerval Scheduling BoTTomUp BoTTomup dynamic programming Unwind recursion Input n s1msn flpufn V1vn Sort jobs by finish times so that f1 5 f2 5 s f Compute pl p2 pn Iterative Compute Opt MO O for j 1 to n Mj maxvj Mpj Mjll

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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

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