Algorithm Design and Analysis
Algorithm Design and Analysis CSE 565
Popular in Course
Popular in Computer Science and Engineering
This 0 page Class Notes was uploaded by Libby Kuhlman on Sunday November 1, 2015. The Class Notes belongs to CSE 565 at Pennsylvania State University taught by Staff in Fall. Since its upload, it has received 21 views. For similar materials see /class/233118/cse-565-pennsylvania-state-university in Computer Science and Engineering at Pennsylvania State University.
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: 11/01/15
Algorithm Design and Analysis V y 1 I LECTURE 16 3 Dynamic Programming 5 0 plus FFT Recap Adam Smith 9242008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne DiscreTe Fourier Transform CoefficienT To poinTvolue Given a polynomial o0 o1 x on1 xn39l evoluoTe if of n disTincT poinTs x0 xn1 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 13 Du 1 a1 yz 1 002 004 we 00201 1 02 y3 1 m3 16 19 00301 1 a3 yH 1 Dn l w2n 1 03301 1 wn 1n 1 0H 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 powers 39 Aevenx 00 02X Cl4x2 an22 xn12 39 Aodd x a1 03X Cl5x2 an21xn12 I Aevenx2 x AoddX2 Conquer EvaluaTe degr39ee Aevenx and Aoddx aT seT of all squares of nTh roofs of unity seT of all nih roofs of uniTy v0 v1 vnZ39l Combine O I I 7 Aw Aevenvk 00k Aoddvk o s k lt n2 Aakquot2 A vk 00k Aoddvk o s k lt n2 Whn n is even There are only n2 possible values of 002k 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 0 1 a0a15quotan1 0 yOquotquot wn ynl 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 000 11 con1 find unique polynomial a0 a1 x an1xquot391ThaT has given values aT given poinTs a0 1 1 1 1 1 391 yo a1 1 ml D2 D3 mn l yl a2 1 m2 D4 D6 w2n 1 yz a3 1 03 06 009 130 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 00 1 0 2 00 3 w n l G 1 1 0 2 04 mm m 2n1 n n 1 03 3 0 6 03 9 D 3n 1 1 w n l D 2n 1 w 3n 1 m n 1n 1 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 CXO Cxl Cx2n1 Bx2n1 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 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 AnAufobiography Dynamic Programming ApplicaTions Areas BioinformaTics ConTrolTheory 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 39 C11 1 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 InTerval Scheduling WeighTed inTer39val scheduling problem Jobj sTar39Ts aT sj finishes aT fJ and has weighT or39 value VJ Two jobs compaTible if They don39T overlap Goal find maximum weighT subseT of muTually compaTible 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 InTerval 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 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 for j Mj MO 0 1 to n empty global ar r ay 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 f1PNfn V1vn Sort jobs by finish times so that f1 5 f2 5 s f Compute pl p2 pn IterativeCompute Opt MO O for j 1 to n Mj maxvj Mpj Mjll
Are you sure you want to buy this material for
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'