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 26 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.
Date Created: 11/01/15
Algorithm Design and Analysis Computational Intractability Polynomial Time Reductions m LECTURE 35 55 Sofya Raskhodnikova Algorithm Design Patterns and AntiPatterns Algorithm design patterns Examples ereedv otn log n intervalscheduling Dividerandrcorlquzr 0n log n FFT Dynamic programming 0 n2 edit distance Dualitv eg MaxFlowetwinCut 0Vl3blparlll2 matching Reduc lOYlS Local SP Fandomlznllmi Algorithm design anllrpallzrrls NPecompleteness OM algorithm unhhelv PSPACErcompleleness otnk Czr llflcallorl algorithm unlihelv Undecidabilitv No algorithm possible Classify Problems According to Computational kequirements Q which problems will we be able to solve in practicev A worhing detinition onNammasonhoodlumitosnnoasitisrm no Those with poivnomiaietime algorithms shortest path Langest path Matching Ebrmnldllrlg Min cut Max cut ZVSAT 375M Pla r l Planar lculur Bipartite vertex caver Vertex caver Primalilv testing Factoring Classify Problems besiderala classitv problems as those that can be solved in polynomialrllmz and those that cannot Provabiv requires exponentialrllme Given aTuring machine does it halt in at most k steps7 eiven aboard position in an nebven generalization of chess can biach guarantee a winv Frustrallng news Huge number ot tundamentai problems have detied classitication tor decades This chapter show that these tundamentai problems are computationally equivalent and appear to be ditterent manitestations ot one reaiiv hard problem PolynomialTime keduction besiderala Suppose we could solve x in polynomialrllmz what else could we solve in ol nomial llmz p y dun t cantuse with reduces tram Reduction Problem x polvnomial reduces to problem v it arbitrarv instances of problem x can be solved using Polvnomial number of standard computational steps plus Polvnomial number of calls to oracle that solves problem v cumpulcllluncll mudei supplemented by special N quot quot quot X Swank V M XSP V piece at hardware that solves instances aw in asinglestep Later in the lecture gtlt gm v Remarksi We pav tor time to write down instances sent to biachbox 2 instances otv must be ot poivnomiai size PolynomialTime keductioh Purpose classitv problems according to relative ditticultv Design algorithms If X 3 v andv can be solved in polynomialrllmz thenx can also be solved in polvnomial time Establish intractabihtv Itx s v andx cannot be solved in poivnomiaietime then v cannot be solved in poivnomiai time Establish equivalence Itx gpv and vs x we use notationx a up tu cast of reduction Simplifying Assumption Decision Problems Search problem Find some structure Examp e r iii i aminimum cut Decision problem X is aset of strings Instance strings Ifxe x x is aYEs instance if xe x is a N0 instance Algorllhm A solves problem x As yes itt s e x Example Does there i39t39 acut of sizes w Seltereducibility Search problem spam decision version Appiles to all NPecomplete problems in this chapter Justities our focus on decision problems Polynomial Transformation Def Problem x ml i mi in e pi eCooh to problem v it arbitrary instances of problem x can be solved using Polynomial number of standard computational steps plus Polynomial number of calls to oracle that solves problem v Def Problem x iiiv i iii i i r Karp to problem v it given any inputx togtlt we can construct an input y such that x is a yes instance of x int y is a yes instance of v We requlr e lyl ta be uf size palynamial in igtlti Note Polynomial lrarisformallori is polynomial reduction Wlthusl one call to oracle for v exactly at the end of the algorithm for X Open question Are these two concepts the same Cautiun KT abuses nutatiun P and blurs distinction Reduction By Simple Equivalence Basic reduction strategies Reduction by simple equivalence keduction from special case to general case keduction by encoding witli gadgets Independent Set INDEPENDENT SEi elven agraph e v E and an integer h is there a subset of vertices s v such that lsl 2 h and for each edge at most one of its endpoints is in 57 Ex Is there an independent set of size 2 67 V23 Ex Is there an independent set of size 2 77 No Q independentset Vertex Cover VERTEX COVER 6iven a graph 5 v E and an integer k is there a subset of vertices S v such that lsl g h and for each edge at least one of its endpoints is in 57 Ex Is there avertex cover of size S 47 V25 Ex Is there avertex cover of size 5 37 No verlex Luver Vertex Cover and Independent 5et Cialm VERTEXVCOVER EP JINDEPENDENTVSU Pf We show 5 is on independent set int ve s is averlex cover 0 independentset verlex Luver Vertex Cover and Independent Set Ciaim VERTEXVCOVER a INDEPENDENTVS Pf We FF show 5 is an independent set iff y e s is avertex coyer Let S be any independent set Consider an arbitrary edge u y s independent us Sorye s uzvrsorvzvrs Thus v e s coyers u y Let y e s be any yertex coyer obserye that u y e E since y is is avertex c er Thus no two nodes in s areJomed by an edge 2 5 independent set Reduction from Special Case to General Case Basic reduction strategies Reduction by simple equivalence Reduction from paint can to general we keduction by encoding with gadgets Set Cover SUCOVER siyen aset u of n eiements a coitection 5 52 subsets of u and an integer in does the these sets whose union is equai to U7 5 o re eXist acoiiection of s h of Sampie appiication Set u of n capabiiities that we wouid iihe our system to h y The ith piece of software proyides the set s U of capabiiities 600i achieye aii n capabiiities using fewest pieces of software Ex a 12 c 7 f Vertex Cover keduces to Set Cover ctairn VERTEXVCOVER g P SELCOVER Pf ewen a VERTEXVCOVER instance 5 v E h we construct a set cover instance whose size equais the size of the vertex cover instance Reduction 0n input c s v E hgt o tput SELCOVER instance ewh UE 5es Ee incidenttoy Correctness ciairn s etrcover of SiZB S k iff vertex cover of size S k 1 as h 6 Reductions by Encoding with Gadgets Basic reduction strategies Reduction bysimpie equiyaience duction from speciai case to generai case inii ii iii H in Sutisfiubility Literai A Booiean yariabie or its negation xi or xi ciause A diSJLmCHOYi on of iiterais C at v E v 1 Comunctive normai form A propositionai o CMCZA ch c4 formuiao that is the commotion AND of ciauses SAT GivenCNF formuiao does it haye asatisfying truth assignment lSAT SAT where each ciause contains exactiy 3 hterais each carrespunds tn a different ycriabie a ZVQVXQAOvarAzvn3ZVZV Ves xtwex Noamfalse 3 Satis ebility keduces to Independent 5et C atm RVSATSPINDEPEN r E U Pf 6tven an tnstance so 01quot 35M we construct an tnstance 6 h of INDEPENDEN 7 ET that has an tndependent set of stze h ff ts sattsttabte Reduc on 0n tnput lt lt1 et c t tn 3 verttces for each ctause one for each hterat Connect a hterats tn actause tn atrtangte Connect hterat to each of tts negattons h hot hat of ctauses m4 Output lt6 hgt Z Z X 6 X2 X It I a n a zvnlwmce viva vazvz 3 Satis ebility keduces to Independent 5et Ctattn s contatns tndependent set ot stze k hot ttt a ts sattsttabte Pf Let S be tndependent set of stze ontatn exacttv one vertex tn each trtangte 52 mg ttmats to and anyothervartantesmasonststentway Truth asstgnrnent ts conststent and 0H ctauses are sattstt 6W n sattstvtng asstgntnent setect one true hterat trotn each trtangte Thts ts an tndependent set ot stze a It I I n h 3 39ZVK7VX3A VZYIzvzlvn Review Bastc reductton strategt es t p equtvatence1NbEtgtENbE e vERTExecovER Spectat case to generat case vEtzTExecovERgP 5350ka Encodtng wtth gadgets aeSATgP JINDEPENDENTVSET Transtttvttv Ifgtlt ng andv gP 2 then x ng Pf tdea Compose the two atgortthms Ex 375M g P INDEPENDENTSUS P VERTEXCOVER g P SELCOVER Include v m the vertex cover Selfkeducibility bectstonprobtetn Search probtetn Does therent t avertex cover otstzes w 39 vertex cover ot tntnttnutn cardtnahtv Settereductbthtv Search pr btetn sP dectston ver Apphes to GH Npecotnptete probtetns tn thts chapter Justtttes our tocus on dectston probtetns Ex to ttnd tntn cardtnahtv vertex cover 0n tnput oeetvgy Btnarv search tor cardtnahtv w o m vertex cover us ug tvt mttsutnmut n no Fmd avertex v such that C 4v has avertex cover of s ze s w 1 7 any vertex tn anv mtn vertex cover th have thts propertv DUVUcaHsto the ordct Recurstvetv ttnd a tntn vertex cover tn 6 v Mt v and ntt hadquot my Algorithm Design and Analysis LECTURE 30 Computational l 5 Intractability Polynomial Time Reductions Adam Smith A Smith based on slides by S Raskhodnikova and K Wayne 11212008 PolynomialTime ReducTion Purpose Classify problems according To r39elaTive difficulTy Design algor39iThms If X s P Y and Y can be solved in polynomialTime Then X can also be solved in polynomial Time EsTablish inTr39acTabiliTy If X s P Y and X cannoT be solved in polynomialTime Then Y cannoT be solved in polynomial Time EsTablish equivalence If X s P Y and Y s P X we use noTaTion X a PY up To cosT of r39educTion Simpliinng Assumption Decision Problems Search problem Find some structure Example Find a minimum cut Decision problem X is a set of strings Instance string 3 If xe X x is a YES instance if xi X is a NO instance Algorithm A solves problem X As yes iff s E X Example Does there exist a cut of size s k Selfreducibility Search problem s PICook decision version Applies to all NPcomplete problems in this chapter Justifies our focus on decision problems Polynomial TransformaTion Def Problem X polynomial reduces Cook To problem Y if arbiTrary insTances of problem X can be solved using Polynomial number of sTandard compuTaTional sTeps plus Polynomial number of calls To oracle ThaT solves problem Y Def Problem X polynomial Transforms Karp To problem Y if given any inpuT x To X we can consTrucT an inpuT y such ThaT x is a yes insTance of X iff y is a yes insTance of Y we require IyI To be of size polynomial in IXI NoTe Polynomial TransformaTion is polynomial reducTion wiTh jusT one call To oracle for Y exachy aT The end of The algoriThm for X Open quesTion Are These Two concest The sarTne CauTion KT abuSes noTaTion sp and blurs disTincTion Reduc rion By Simple Equivalence Basic r educ rion sTraTegies I ReducTion by simple equivalence I Reduc rion from special case To general case I Reduc rion by encoding wiTh gadgeTs IndependenT SeT INDEPENDENT SET Given a graph G V E and an inTeger39 k is There a subseT of ver39Tices S E V such Thcn ISI 2 k and for each edge cn mosT one of iTs endpoints is in 5 Ex Is There an independenT seT of size 2 6 Yes Ex Is There an independenT seT of size 2 7 No O independenf 36139 Ver39Tex Cover39 VERTEX COVER Given a graph G V E and an inTeger39 k is There a subseT of ver39Tices S E V such Thcn ISI 5 k and for each edge cn leasT one of iTs endpoints is in 5 Ex Is There a ver39Tex cover39 of size s 4 Yes Ex Is There a ver39Tex cover39 of size s 3 No ver39Tex cover39 Ver Tex Cover39 and IndependenT SeT Claim VERTEXCOVER EP INDEPENDENTSET Pf We show 5 is an independem seT iff V S is a ver39Tex cover O independem 36139 ver39Tex cover39 VerTex Cover and IndependenT SeT Claim VERTEXCOVER EP INDEPENDENTSET Pf We show 5 is an independenT seT iff V S is a ver39Tex cover39 gt LeT S be any independenT seT Consider an ar39biTr39ar39y edge u v SindependenTuSorvS gt uEVSor39vEVS Thus V 5 covers u v lt LeT V S be any ver39Tex cover39 Consider39 Two nodes u E S and v E S Obser39ve Thcn u v i E since V S is a ver39Tex cover39 Thus no Two nodes in S are Joined by an edge gt 5 independenT seT Reduc rion from Special Case To General Case Basic r educ rion sTraTegies I Reduc rion by simple equivalence I Reduc rion from special case To general case I Reduc rion by encoding wiTh gadgeTs SeT Cover39 SET COVER Given a seT U of n elemenTs a collecTion 1 2 Sm of subseTs of U and an inTeger39 k does Ther39e exisT a collecTion of s k of These seTs whose union is equal To U Sample applicaTion m available pieces of sofTwar39e SeT U of n capabiliTies ThaT we would like our39 sysTem To have The iTh piece of sofTwar39e provides The seT S Q U of capabiliTies Goal achieve all n capabiliTies using fewesT pieces of sofTwar39e Ex U1234567 k2 5137 5424 52345 S55 531 56 1 267 Ver rex Cover Reduces To SeT Cover Claim VERTEXCOVER s P SETCOVER Pf Given a VERTEXCOVER insTcmce G V E k we consTr39ucT a seT cover39 insTcmce whose size equals The size of The ver39Tex cover39 insTcmce ReducTion On inpuT lt 6 V E kgt OquuT SETCOVER insTcmce kk UE SveEEeincidenTTov Cor39r39ecTness claim SeTcover39 of size s k iff ver39Tex cover39 of size s k VERTEX COVER e 7 62 63 e4 e6 61 e5 SET COVER U1234567 k 2 5a37 5b24 5c 3 4 5 6 sd 5 se1 sf1267 Reduc rions by Encoding wi rh Godge rs Basic r39educTion sTr39oTegies ReducTion by simple equivalence ReducTion from special case To general case ReducTion by encoding wiTh godgeTs Satisfiability Literal A Boolean variable or its negation xi 0r xi Clause A disjunction OR of literals C x1 V g V 3 3 Conjunctive normal form A propositional q C1 A02 A 03A C4 formula lt1 that is the conjunction AND of clauses SAT Given CNF formula I does it have a satisfying truth assignment 3SAT SAT where each clause contains exactly 3 literals each corresponds to a different variable Ex vazvx3Ax1vx 2vx3x2vx3AEvgvg Yes X1 true x2 true X3 fal3e 3 SaTisfiabiliTy Reduces To IndependenT SeT Claim 3SAT s P INDEPENDENTSET Pf Given an insTance lt1 of 3SAT we consTr39ucT an instance 6 k of INDEPENDENTSET ThaT has an independenT seT of size k iff I is saTisfiable ReducTion On inpuT lt I gt LeT G conTain 3 ver39Tices for each clause one for each IiTer39al ConnecT 3 IiTer39als in a clause in a Triangle ConnecT IiTer39aI To each of iTs negaTions k lt1gtI k of clauses in I OquuT lt6 kgt 3 SaTisfiabiliTy Reduces To IndependenT SeT Claim 6 conTains independenT seT of size k lt1gt iff I is saTisfiable Pf gt LeT S be independenT seT of size k S musT conTain exachy one verTex in each Triangle 561 These ferd3 10 True 4 and any o rher variables in a consis ren r way TruTh assignmenT is consisTenT and all clauses are saTisfied Pf lt Given saTisfying assignmenT selecT one True liTeral from each Triangle This is an independent seT of size k Review Basic r39educTion sTr39aTegies Simple equivalence INDEPENDENTSET a P VERTEXCOVER Special case To general case VERTEXCOVER s P SETCOVER Encoding wiTh gadgets 3SAT s P INDEPENDENTSET Tr39ansiTiviTy If X s P Y and Y s P Z Then X s P Z Pf idea Compose The Two algor39iThms Ex 3SAT s P INDEPENDENTSET s P VERTEXCOVER s P SETCOVER Algorithm Design and Analysis a 1 ti LECTURES 2224 Counting Simple Paths a i E Network Flow 0 Maximum FOW 0 Minimum Cut 0 F 0rdFulkerson A Smith A Smith based on slides by S Raskhodnikova and K Wayne 10152008 Review QuesTion How many simple paThs of lengTh k can Ther39e be in a graph wiTh n nodes Consider following code ModifiedDFSu isT paThsofar39 If u is in paThsofar39 r39eTur39n Else Add u To paThsofar39 If sizepaThsofar39ltk For all neighbors v of u ModifiedDFSvpaThsofar39 Does This run in Time 02k polyn Network Flow and Linear Programming 10152008 A Smith based on Slides by S Raskhodnikova and K Wayne Sovie r Rail Ne rwork 1955 Reference 0n fhe hisfory of fhe fransporfa on and maximum ow probems Alexander Schrijver in Ma rh Programming 91 3 2002 Maximum Flow and Minimum Cu r Max flow and min cuT Two very rich algor39i rhmic problems Cor39ner39sTone problems in combina ror39ial opTimizaTion Beau riful maThemaTical dualiTy NonTr39ivial applicaTions r educTions Data mining OpenpiT mining PPOJZC l SelecTion Air39line Scheduling Bipar TiTe maTching Image Segmentation ClusTer39ing NeTwor39k connecTiviTy NeTwor39k r eliabiliTy DisTr39ibuTed compuTing EgaliTar ian sTable maTching NeTwor39k inTr39usion deTeCTion MulTicamer39a Scene r39econsTr39ucTion Da ra pr39ivacy Many many more Minimum Cu r Problem Flow neTwork AbsTracTion for maTerial flowing Through The edges G V E direcTed graph no parallel edges Two distinguished nodes 3 source T sink ce capaciTy of edge e 9 10 4 15 15 10 source 5 k 8 f 10 sink 15 4 6 15 10 capaci ry 39 4 30 7 CuTs Def An 31 cm is a par TiTion A B of V wiTh s E A and T E B Def The capacity of a cuT A B is capAB 2 ce 2 out ofA C9 6 15 10 Capaci ry 10 5 15 30 30 CuTs Def An 31 cm is a par TiTion A B of V wiTh s E A and T E B Def The capacity of a cuT A B is capAB 2 ce eoutofA 10 4 15 15 10 lo a A 4 6 15 15 10 Capaci ry 9 15 8 30 4 30 7 62 Minimum Cu r Problem Min sT cuT problem Find an 31 cuT of minimum capaciTy 1 0i L A 15 30 7 10 Capaci ry 10 8 10 2 28 Flows Def An sT flow is a funcTion 1 from E To real numbers ThaT saTisfies For39 each e E E 0 s fe s ce capaciTy For each v E V s T E e E e conservaTion emtov eoutofv Def The value of a flow 1 is Vf 2 fe eoutofs 0 9 4 o 10 4 4 15 15 O 10 O 4 4 C9 5 8 C6 10 D o o 4 o 6 15 o 10 capaci ry gt 15 flow gt O 0 Value 4 Flows Def An sT flow is a funcTion 1 from E To real numbers ThaT saTisfies For39 each e E E 0 s fe s ce capaciTy For each v E V s T E e E e conservaTion emtov eoutofv Def The value of a flow 1 is Vf 2 fe e out of s 10 6 10 4 4 15 15 O 10 3 8 8 9 5 8 C6 10 CD 1 10 4 o 6 15 o 10 capaci ry gt 15 flow gt 11 H GD 30 6 Value 24 Maximum Flow Problem Max flow problem Find sT flow of maximum value 9 9 10 1 9 10 4 O 15 15 0 1o 4 8 9 C9 5 8 C6 10 CD 4 10 4 0 6 15 o 10 capaci ry gt 15 flow gt 14 14 Value 28 Flows and CuTs Flow value lemma LeT f be any flow and leT A B be any sT cuT Then The neT flow senT across The cuT is equal To The amounT leaving 3 E e E e vf eoutofA eintoA 6 9 C5 10 6 10 4 4 15 15 0 10 3 8 8 5 gt 8 lt63 10 a A 1 10 4 0 6 15 O 11 quot39 v I 24 quot Cl U6 5 so a Flows and CuTs Flow value lemma LeT f be any flow and leT A B be any sT cuT Then The neT flow senT across The cuT is equal To The amounT leaving 3 Efe e out ofA E e vf eintoA X W 0 11 30 W l 2 10 0 1o 4 4 3 5 3 A 4 o 15 11 4 CD Value608111 Flows and CuTs Flow value lemma LeT f be any flow and leT A B be any sT cuT Then The neT flow senT across The cuT is equal To The amounT leaving 3 E e E e vf eoutofA eintoA 6 9 10 O 6 10 4 4 15 15 O 10 3 g 8 5 3 8 CelD 10 A 1 10 4 0 6 15 O 15 10 11 11 Value1048O10 4 30 l 7 24 Flows and CuTs Flow value lemma LeT f be any flow and IeT A B be any 31 cm Then 2 fe E fe Vf eoutofA eintoA Proof Vf E f e eoutofs by flow conserva rional Terms gt E E 2 excepTVSGF60 vEA eoutofv eintov 2 fe 2 t eoutofA eintoA QuesTion Two problems min cu r max flow How do They r39ela re Flows and CuTs Weak duaIiTy LeT f be any flow and eT A B be any sT cuT Then The value of The flow is aT mosT The capaciTy of The cuT CuT capaciTy 30 2 Flow value 5 3O 15 9 so Big OpTimizaTion Idea 1 Look for39 sTr39ucTur39al consTr39ainTs eg max flow 5 mincuT CapaciTy 30 Flows and CuTs Weak dualiTy L61 1 be any flow Then vf s capA B for any 31 cm A B Pf vf Effe E e eoutoA eintoA S E fe eoutofA s 2 Ce e out ofA capAB Cer rifica re of Op rimali ry Corollary LeT f be any flow and la A B be any sT cuT If vf capA B Then 1 is a max flow and A B is a min 31 cm Value of flow 28 Cut capaci ry 28 2 Flow value 5 28 10 1o 4 o 4 g 9 5 3 8 10 A 4 o 15 14 4 Towards a Max Flow Algor i rhm Greedy algor39iThm STar39T wiTh fe O for all edge e E E Find an 31 paTh P where each edge has fe lt Ce Augmem flow along paTh P RepeaT unTil you geT sTuck 1 a 39O 0 20 10 30 O 10 20 0 0 Flow value O W Towards a Max Flow Algor i rhm Greedy algor39iThm STar39T wiTh fe O for all edge e E E Find an 31 paTh P where each edge has fe lt Ce Augmem flow along paTh P RepeaT unTil you geT sTuck 1 20 E a 20 10 30 EEO 10 20 0 mg 20 Flow value 20 W Towards a Max Flow Algorithm Greedy algorithm Start with fe O for all edge e E E Find an st path P where each edge has fe lt Ce Augment flow along path P Repeat until you get stuck locally optimality 7b global optimality 10 quot ll 393 gr39eedy 20 20 3 A 42 U opt 30 Residual Graph Original edge e u v E E COPGCW Flow fe capacity ce 17 6 flow Residual edge quotUndoquot flow sent e u v and eR v u Residual capacity Q 11 j ce fe if e e E 6 cfe fe if eR E E residual capacity residual capacity Residual graph 6f 2 V E Residual edges with positive residual capacity Ef e 1 fe lt ce U eR ce gt O FordFulker39son Algor i rhm 4 capaci ry 10 2 8 j 10 10 9 Io FordFulker39son Algor i rhm flow capaci ry 1 Flow value O FordFulker39son Algor i rhm 2 4 flow capaci ry G1 8 12 8 0 10 2 o 6 0 10 o i ON 8 38 s 10 3 9 5 V U 10 39 00E 0 Flow value O 2 4 4 residual capaci ry Gf 10 2 8 E 10 10 9 103 FordFulker39son Algor i rhm 1 Flow value 8 2 2 8 E 10 FordFulker39son Algor i rhm o 2 4 61 1o 8 1o 8 22 O E 6 J 2 s 10 9 9 2 4 Gf 10 2 8 6 sf1o Js oo o 1 0 31 18 6 10 loo 10 T Flow value 10 1o 1o 7 7 AK FordFulker39son Algor i rhm 2 4 4 61 loKs K8 10 22 8 66 10 O 38 8 10 s 10 3 5 V 9 39 Flow value 16 FordFulker39son Algor i rhm X 2 4 4 G loCRX 7 39 10 20 8 66 10 x 9 i 3N 10 s 10 3 9 5 V Flow value 18 2 2 2 t 4 Gf 8 10 2 86L 2 5 2A1 8 8 FordFulker39son Algor i rhm Flow value 19 FordFulker39son Algor i rhm CUT capaci ry 19 Flow value 19 AugmenTing PaTh AlgoriThm Augmentf c P b lt bottleneck P Min residual capaci ry of an edge in P foreach e E P if e E E f e lt f e b forward edge else f e lt f e b reverse edge return f Ford FulkersonG s t c foreach e E E fe 0 Gf residual graph while there is an s t path P in GQ f t Augmentf c P update Gf return f FordFulkerson Summary so far FordFulkerson While you can Greedin push flow UpdaTe residual graph Lemma 1 This oquuTs a valid flow Proof Check conservaTion condTions see book STiII To do Running Time in parTicular TerminaTion How good a flow Running Time AssumpTion All capaciTies are inTegers beTween 1 and C InvarianT Every flow value fe and every residual capaciTy cf e remains an inTeger ThroughouT The algoriThm Theorem The algoriThm TerminaTes in aT mosT vf s nC iTeraTions Pf Each augmenTaTion increase value by aT leasT 1 Running Time of FordFulkerson OmnC Space Omn Corollary If C 1 FordFulkerson runs in Omn Time MaxFlow MinCUT Theorem AugmenTing paTh Theorem Flow 1 is a max flow iff There are no augmenTing paThs Maxflow mincuT Theorem EliasFeinsTeinShannon 1956 FordFulkerson 1956 The value of The max flow is equal To The value of The min sT cuT Pf We prove boTh simulTaneously by showing i iii are equivalenT i There exisTs an sT cuT A B such ThaT vf capA B ii Flow 1 is a max flow and AB is min sT cuT iii There is no augmenTing paTh relaTive To 1 i 2 ii This was The corollary To weak dualiTy lemma ii 2 iii We show conTraposiTive LeT f be a flow If There exisTs an augmenTing paTh Then we can improve 1 by sending flow along paTh Proof of MaxFlow MinCUT Theorem iii gt i LeT f be a flow wiTh no augmenTing paThs LeT A be seT of verTices reachable from s in residual graph By definiTion of A s E A By definiTion of f T 6E A ObservaTion No edges of The residual graph go from A To B original neTwork Claim 1 If e goes from A To B Then fe ce Proof OTherwise There would be residual capaciTy and The residual graph would have an edge A To B Claim 2 If e goes from B To A The eoutEOfAfe einEtO e Proof OTherwise residual edge 2 ce would go from A To B eoutofA capAB lt A H V II Running Time AssumpTion All capaciTies are inTegers beTween 1 and C InvarianT Every flow value fe and every residual capaciTy cf e remains an inTeger ThroughouT The algoriThm Theorem The algoriThm TerminaTes in aT mosT vf s nC iTeraTions Pf Each augmenTaTion increase value by aT leasT 1 There are aT mosT nC uniTs of capaciTy leaving source s Running Time of FordFulkerson OmnC Space Omn Corollary If C 1 FordFulkerson runs in Omn Time InTegraliTy Theorem If all capaciTies are inTegers Then There exisTs a max flow 1 for which every flow value fe is an inTeger Pf Since algoriThm TerminaTes Theorem follows from invarianT Algerithm Design and Analysis LECTURE 6 Topological ordering Greedy Algorithms Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 952008 Read on your own Graph bipartiteness DF S implementation 0 Homework notation loga l log DY smallest integer 2 1 ceiling Useful property 1 g lt 1 1 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne 952008 Last lecture BFS Recall Digraph G is strongly connected if for every pair of vertices smt and smt Question Give an algorithm for determining if a graph is connected What is the running time 952008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Strong Connectivity Algorithm Lemma 6 is strongly connected if and only if for any node 5 every other node t has paths to and from 5 Theorem Can determine if G is strongly connected in Om n time Pf Pick any node s I Run from 5 in reverse orientation ofevery edge in G Run BFS from s in 6quot Return true iff all nodes reached in both BFS executions Correctness follows immediately from the previous lemma strongly connected not strongly connected Direc red Acyclic Graphs Def An DAG is a direcTed graph Tha r contains no direcTed cycles Ex Precedence consTrain rs edge vi VJ means vi musT precede VJ Def A Topological order of a direcTed graph G V E is an ordering of HS nodes as v1 v2 vn so That for every edge vi VJ we have i lt j a DAG a topological ordering Precedence Cons rr39ain rs Precedence consTr39ain rs Edge vi VJ means Task vi musT occur39 before VJ Applications Cour39se pr39er39equisi re gr39aph cour39se vi musT be Taken befor39e VJ Compila rion module vi musT be compiled befor39e VJ Pipeline of compu ring jobs ou rpu r of job vi needed To determine inpu r of job VJ Dir39ecTed Acyclic Gr39aphs Lemma If G has a Topological or39der39 Then G is a DAG Pf by conTr adicTion Suppose ThaT G has a Topological or39der39 v1 vn and ThaT 6 also has a dir39ecTed cycle C LeT39s see whaT happens LeT vi be The lowesTindexed node in C and leT VJ be The node jusT befor39e vi Thus VJ vi is an edge By our39 choice of i we have i lt j On The oTher39 hand since VJ vi is an edge and v1 vn is a Topological order39 we musT have j lt i a conTr39adicTion the directed cycle C 000000 the supposed topological order v1 vn Direc red Acyclic Graphs Lemma If G has a Topological order Then G is a DAG Q Does every DAG have a Topological ordering Q If so how do we compu re one Dir ec red Acyclic Gr39aphs Lemma If G is a DAG Then G has a node wi rh no incoming edges Pf by con rr39adic rion Suppose That 6 is a DAG and every node has at leasT one incoming edge Let39s see what happens Pick any node v and begin following edges backwar39d from v Since v has at leasT one incoming edge u v we can walk backwar39d To u Then since u has at leasT one incoming edge x u we can walk backwar39d To x Repea r until we visi r a node say w Twice Let C denoTe The sequence of nodes encoun rer39ed between successive visi rs To w C is a cycle Topological Sor39Ting AlgoriThm Running Time Theorem Algor39iThm finds a Topological order in Om n Time Pf MainTain The following infor39maTion 7 count w 2 remaining number39 of incoming edges S seT of remaining nodes wiTh no incoming edges IniTializaTion Om n via single scan Thr39ough gr39aph UpdaTe To deleTe v r39emove v from S decr39emenT count w for39 all edges from v To w and add w To 5 if c count w l ll l39S 0 This is 01 per39 edge AlTer39naTive algor39iThm ModificaTion of DFS exercise Design technique 1 Greedy Algorithms A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Greedy Algorithms Build up a solution to an optimization problem at each step shortsightedly choosing the option that currently seems the best Sometimes good Often does not work 952008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Interval Scheduling Problem Job j starts at sj and nishes at Two jobs are compatible if they do not overlap Find maximum subset of mutually compatible jobs a b g a g h 0 l 2 3 4 5 6 7 8 9 10 11 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Time 952008 Possible Greedy Strategies Consider jobs in some natural order Take next job if it is compatible with the ones already taken Earliest start time ascending order of sj Earliest nish time ascending order of Shortest interval ascending order of fj sj Fewest con icts For each job j count the number of con icting jobs cj Schedule in ascending order of c J 952008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Greedy Counterexamples for39 earlies r starT Time for shortest interval for fewest conflicts 952008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Algorithm Design and Analysis LECTURE 20 Dynamic Programming LCS Sofya Raskhodnikova m Longest Common Subsequence LCS Given two sequences xl m andyl n find a longest subsequence common to them both a quotat the x AB C B D A B BCBA LCSxy yBDCABA g Bruteforce LCS algorithm Check every subsequence of xl m to see ifit is also a subsequence ofyl n Analysis Checking 0n time per subsequence 2 subsequences of x each bitvector of length m determines a distinct subsequence of x Worstcase running time 0n2 exponential time m Dynamlc programming algorlthm Simplification 1 Look at the length of a longestcommon subsequence 2 Extend the algorithm to find the LCS itself Notation Denote the length of a sequence s by Isl Strategy Consider pre xes of x and y Define cij LCSxl i y1 j 39 Then cm n LCSx y W Recurswe formulation ci71j71 1 ifxi yj CD J maxciilj cijil otherwise Base case cij0 if i0 orij Case xi yj l 2 Xi y 7 The second case is similar Dynamicprogramming m Optimal substructure An optimal solution to aproblem instance contains optimal solutions to subproblems v If z LCSx y then any prefix of z is an LCS of a prefix ofx and a prefix ofy Recursive algorithm for LCS LCSx y ij ignoring base cases ifxi yj then cij LCSx y 1211 1 else cij rnax LCSx y i71j LCSx y ij71 return cij Worse case xi r39 yj in which case the algorithm evaluates two subproblems each with only one parameter decremented Height m n 2 work potentially exponential Recursion tree Height m n 2 work potentially exponential but we re solving subproblems already solved Dynamicprogramming Overlapping subproblems A recursive solution contains a small number ofdistinct subproblems repeated many times The number of distinct LCS subproblerns for two strings of lengths m and n is only mn Memoization algorithm Memoization After computing a solution to a subproblem store it in a table Subsequent calls check the table to avoid redoing work LCSQC y i j if ci j NIL then ifxi y then ci J lt LCSQC y 71 13971 1 WW else ci j lt maxLCSx y i71j LCSQC y i 14 Time 2 mn constant work per table entry Space 2 mn as before E Dynamicprogramming 39 IDEA A B C D B A Compute the r E El I mam Dynamicprogramming IDEA Compute the table bottomup B Time 2 mn D Dynamicprogramming IDEA Compute the table bottomup B Time 2 mn Reconstruct LCS by tracing backwards B A IDEA Compute the table bottomup B Time 2 mn Reconstruct LCS by tracing backwards Space 2 mn B Exercise 0minm n Algorithm Design and Analysis Divide and Conquer Fast Fourier Transform m LECTURES 17 and 18 3 Sofya Raskhodnikova Fast Fourier Transform Applications Applications o iics acoustics quantum physics Telecommunications control systems signal processing speech recognition data compression image processing DVD JPEe MP3 MRI CAT scan Numerical solutions to Poisson s equation We FFF is ane afine lrulygreal cumpulalluna 7y It nas enanged ine different Wiinaui tne FFT harles van Lucin Fast Fourier Transform Brief History sauss 1305 moo Analyzed periodic motion of asteroid Ceres Rungeexonig1924 Laid ineoreiicai groundwork banieisonetanczos 1942 EffiCieni aigoriinrn Cooieyeiueey 1965 Monitoring nuclear tests in Soviet Union and aclwig submarines Rediscovered and popularized FFT Imporionee noi fully reaiized uniii advent of digiioi compuiers Polynomials Coefficient Representation Polynomial coeffieienirepreseniaiion Ax ea aix a2x2 oixquot Ba ba bixb2x2bnixquotquot Add 0n ariinrneiic operations Amwm o0 Jerome was aM semis Evaluate 0n using Homer s rneinod Am ea xa xa1 xeH xaH Multiply convolve 0n2 using bruie force we AxgtltBx z a x where a ZeabH e Polynomials PointValue Representation Fundameniai ineorein of oigebro Gauss PhD inesis A degree n polynomial niin complex coeffieienis nos n complex roois Corollary A degree nei polynom iai m is uniquely specified by iis evaluation at Vi dlSllYiCl values of x y e x Polynomials PointValue Representation Polynomial poinievaiuerepreseniaiion Add 0n ariinrneiic operations AxJBx x0yatzoxniynizM Multiply 0n bui need 2nei poinis Axgtlt Rte Xa yogtlt Ialt Ami me 14H Evaluate 0m using Lagrange s fornuio Mira M A e L m 53mm J er Converting Between Two Polynomial kepresentutions Tradeoff Fast evaiuation or fast muitipiication We want bothi Calf tiewt Pomp u 600i Make aH ops fast bv efficientiy convening beiween iwo represeniaiions 1o yavmm coefficient painfrvaiue mommaquot epeeiiaivi Converting Between Two Polynomial kepresentutions Brute Force Coefficient io pointrvaiue given a poivnomiai a e a x aquot xm evaiuaie ii ai n disiinci poims x 0711 for matrixrvectar muitip 1v Va 1 q a 21 I J a 342 x I 1 Q E 1 1 31 1 m 5 om for Eaussia v eiininanon iionvnnonv matrix ilt invmioi in Wane poinievaive io coefficient siven ndisiinci pointsxn x d v vm find unique poivnoiniai an ax MW inai nas given vaiues ai given poinis ini Coefficient to PointValue Representation Intuition Coefficient io poinievaine given a poivnoiniai an e ax imxm evaiuate ii ui n disiinci poinis x xm Divide Break poivnoiniai up inio even and odd powers Agtlt an ax 02x2 e 03x3 04x4 05x5 11be 07x7 05x3 A Mix AWKX r X MAX Iniuiiion Choose iwo poinis 10 be 1 1Avn1391amp111 V Ae1AW1e1Am1 cenm mendymmouroegmsn at Zoom by evduanngtm pntymmmii at degrees 1 pain 111 Coefficient to PointValue Representation Intuition Coefficient io pointrvaiue given a poivnomiai a 1 e a x aM xm evaiuaie ii ai n disiinci poinis x W x agtlt 02x2 e 03x3 04x4 05x5 avd 07x7 Amm an 02x 04x2 a Am x a 03x 05x2 07x3 M x gt x MAX Mex Am x2 x MAX Divide Break poivnoiniai up inio even and odd powers A Inmiiion cnoose four poinisio be 1 i Ammanquot 1e1Am1 mimeponmomoegmsn A i AWH i AMH at 4 points evnunnngtm polynomian AWMMVUV Mm ufdegrae nth mts Dlscrete Fourier Transform Coefficient io pomvrvaiue given a poivnomiai an e agtlt aMxM evaiuaie ii ai n disiinci poinis x x Key idea cnoose xk bk wneie m is principai nm iooi of vniiv ya i 1 yi I 52 h 1 a3 3 K I m3 39 mi Discrete Fourier transform Fouriermatrix a Roots of Unity Def Anivw v min is acompiex number x sncn inai xquot 1 Faci The nm wars of uniiv are m m m where m e 2Wquot pf My Ezmiw Niyi 421 1 Faci Tne n noois of unity are v v wu wnene v e 4mm Faei m2v and man Fast Fourier Transform 600i Evaiuaie a degree we poiynomiai Am an aw x at us w of mi m m w was Break poiynomiai up we even and odd powers A x an agxo 04x2 Max AD X 7 a o 03x o 05X o o qjQV XWU Agtlt AWM 39 gtlt MAX Conquer Evaiuaie degree MM and Amgtlt a m w roots of unity quot v vnH Combine Mm FAWM w MW O ks n2 V m a Maw2 Ammy M Ammk o s w n2 vi we 39 a 2 gym2 2 FFI39 Algorithm snin swagwand i Jf n in mumn 3 i wenrw ani mmz agavam aw idmdmr wz1i Puma2 ayayammmy fork0ton21i d o ewm gtlt x t axb dg Yw x39d dx i return iYm39YpUYIJi FFI39 Summary Theorem FFT aigoriihm evaiuaies a degree n71 poiynomiai a each of m w roots of unity in om iog n steps assumsn 5 WWW 2 Running Mme T2n 2m om 2 Tm om iog n Recursion Tree W lkkakrlalv perfeci mm 2m a aquot a zquot a 2 n 2 a w I a 1 Wu m m m m m m n bywmsea mam V u aw m yqltwquot mi caefficiem pmmrvaiue mmm mmm Inverse DFT PointValue to Coefficient kepreseniuiio 600i 6W m vaiues yu ym of adegree n71 poiynomiai a m n aims m m mquotquot ma unique poiynomiai an a x MW that has given vaiues ar given pawns 4 1 l I ya I m is y I a m n l 4439 at y 1 mm NW mama Emma 04 i Inverse an Faurier mmrix inverse m4 Inverse FFI39 Ciaim Inverse of Fourier mamx is given by foiiowmg formuia 1 I I 1 1 1 4 m4 m4 may J I 4 W was mam Gvu v Ara mas m4 mi I mu ame Emmi mm uence To compute inverse FFT appiy same aigoriihm but use Vi Conseq ar 2 remn as principai W root of My and was by Inverse FFI39 Proof of Correctness claim FH and 6H are inverses Pf ier u 161 71 a I ihzlr iVquot 115 m 39 quotE a memo summatirn llmma Summation lemma Let m be aprincipal tim root of unity Then M w n ke mnd m E o other If k is a multiple of n then M 1 2 Each ti h root of unity d is aroot of xquote1x e 1 1 X i 8 i x itaJK 1 we nave1 d 12 MW EO 2 sums too Inverse FFT Summary Ine rem Inverse FFT algoritnm interpolates a degree net polynomial glvzrl values at eac o tne ntr roots ot willy in otn log n steps assumes n i n Dawn a 2 0n lag n agreeinga mtm mm er caefflclent quot l 39 paintrvalue representation represemmlmi Inverse FFT Algorithm unto so maul l Jf tn i I turn 3 wenwow o swtnzg aways a tdgdndoyc utta2 313aghmzwl furk 17 Eon2711 use m n t 9 6 icy hm 1 eruIn yoryomyio w t lxd di1lti Polynomial Multiplication Ineorem Can multiply two degree net polynomials in 0Vl log n steps meant no mantanon kiwi i AM bun11 palmrvalue multiplicatian 391 it u 4quot Rio wHl tamoxcuiLa xw comm rlprlslmn lan 9M EOtEt Integer Multiplication Integer multiplication Given two n bit integers a aM 0 00 and b b 111 compute tneir product c ax b wk 4e Convolution algoritnm Ammam xm z Form two polynomials Note a A2 1 32 Compute Cx AgtltgtltBgtlt Evaluate C2 agtlt b nning tim 0tl logncornplex in i 8x be bix b2x2 bHxquotquot Theory ScnonnageeStrassen 19711 otnlogn log log nitr irr n Mal 1lrlFlll 2rP2ml Slale2007 otn logrl2 W39quot i r Practice 5w Multiple PPBClSlJ Aritiimetic Library 6MP proclaims to be the tastest bignum library on tne planet 1 It uses brute torce Karalsuba and FFT depending on tne RNA Secondary Structure Problem Algorithm Design and Analysis RNA Strtng B bb2 th over alphabetAC e U Secondary structure RNA tends to loop back and form base patrs wttn ltsetf Thls structure ls essentlat for understandlng behatlor of m LECTURE 22 notecute 3 Dynamic Progra ng Ex cuccauucacccaaucmcuccucscuaccsccaca RNA Secondary Structure Shortest Paths Sofya Raskhodnikova b W as w RNA Secondary Structure RNA Secondary Structure Examples Secondary structure A set of patrs s t by blthat sattsty Examples w soneCrtce 5 ts a matcntng and eacn patr tn 5 ts aWatsone 6 Crle complement Aeu woos or sec 9 6 6 6 No Sharp turns 1 The ends of eacn patr are separated by at least 4 R U tnteryentng bases Ifb bge s tnen NJ 7 Nonecrosstng If y bl and bk by are lwopalr s tns tnen we Amu Amu cannothavelltkltJltt Li L has pat Free energy Usual hypothests ts that an RNA molecule wtll form the secondary structure wttn tlne opttmum total free energy approxtmat oynumou at has I AusussccAU Aucccccru AsuussccAu soal etyen an RNA molecule B bb2 b ttnd a secondary structure 5 lt4 tnat maxlmlzzs tne number of base patrs ak snap turn srosstno RNA Secondary Structure Subproblems Dynamic Programming Over Intervals Ftrst attempt oPm Notatton om maxlmum number of base patrs tn asecondary maxlmum number of base patrs tn asecondary structure of tne structure of tne substrtng b b nbl substrtng 21 Mb db Basecase IleJrlt m C quot quot e om o by noesnarp turns condttton Base bl ts not tnyolyed tn apatr e om oPTtttel Case 2 Base by patrs wttn b for some ts M J 7 4 e nonecrosstng constratnt decouples resulttng subeproblems bttttculty Results tn two subeproblems e 0th 1 t max otht tel t OPTtolJrl Ftndtng secondary structure tn bb2 b smut too may can no ts new Ftndtng secondary structure tn beW M k me not depart We umwusonecnet cmptmts Bottom Up Dynamic Programming Over Intervals Q Whai order to soive inc subrprobizms7 A Do snorizsi inizrvais first 1 2 mo 1 1 r k Compute tau 1 I tum MU nl Anemia Time ow Spac 0n2 e r I Find ino secondary siruciurz inai achieves ino max yaiao Dynamic Programming Summary Recipe Recursivziy define yaiao of opiimai soiaiion Compuiz vaiuz of opiimai soiuiion Construct opiimai soiuiion from computed information Dynamic programming izcnniquzs Binarychoicz woignioa inioryai scnodaiing Muhirwaychoicz sogmoniodioosisqaaros H i i Addinganzwvariabiz LCSknapsack Dynamic programming over inizryais RNA secondary siruciurz Toprdown memoizaiion vs bottomrup dirroroni poopio have different intuitions Shortest Paths snoriosi pain probiom eiyon a dirociod graph 5 v E Wiin 2ng i wzignis CW find snorizsi pain from nodz s to nodz uihwmgmm migms Ex Nodzs rzprzszni agznis in a financiai sziiing and cw is cosi of ironsaciion in wnicn no buy from agent y and 52H immodiaioiy io w m v a 5 Jo A on qlt ii is a A an a a4 shortest Paths Failed Attempts Duksira Cari raii in ihzrz oro nogaiiyo 2ng cosis 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 g g g i h o 1 2 3 4 5 6 7 8 9 10 013m maX v1 OPTp OPTj1 Time Weigh red In rer39val Scheduling Memoiza rion Memoiza rion S ror39e r39esul rs of each subproblem in a Table lookupasneeded Input n slm s flpu f V1mV In In Sort jobs by finish times so that f1 5 f2 5 s fn Compute pl p2 pn for j 1 to n Mj empty MO O global ar39r39ay M Compute Optj if Mj is empty Mj maxwj M Compute Optpj M Compute Optj 1 return Mj Equivalent olgori rhm Bo rTomUp Bo r romup dynamic programming Unwind recursion Input n 1sn I f1fn I V1Vn Sort jobs by finish times so that f1 5 f2 5 s f 9 Compute p1 p2 pm how fast Iterative Compute Opt M0 0 for j 1 ton 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 EGG emf 2 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 l 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 j 0 OPTJ min ez j c 0PT139 1 otherwise 15 139 s j 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 for Onz pairs On per pair using previous formula Algorithm Design and Analysis Divide and Conquer Closest Pair of Points m LECTURE 13 3 Sofya Raskhodnikova mm m Revrew questions Guess the solution to the recurrence Tn8Tn2cn Answer 9013 Draw the recursion tree for this recurrence a What is its height Answer hlog n b What is the number of leaves in the tree Answer 8quot 8mg nbg 82 n3 mm A laquot Review questions recursion tree Solve Tn8Tn2cn 5quot quot 77 En CW2 CnZ 4m M8 8 CW4 CW4 0024 ll4 16m I 91 Total cnl44243n2 013 geometric series mm W Appendix geometric series n1 x for x r39 l lxx2x 1 lxxzi for xltl 1 Return to last slide viewed mm A laquot Closest Pair of Points Closest palr elm n palms m we plane ma apalr Wlm smallest Euclldean dlslarlce between them Fundamzmal geomelrlc prlmlllvz Graphlcs computer VlSlan geograpth lrlformallorl systems molecular modellrlg all llam canlral Speclal case of nearest nelghbor Euclldearl MST Veronol as elm W mm as mm m m mil 3le force Check all palr s of palms p and q Wllh W2 comparlsons 17b verslorl om log n easy lf palms are on a llrle Assumpllon No lwo palms have same gtlt coordlnale ta mukl pamlallan clmmr Closest Pair of Points First Attempt Dlvldz Subrdlvlde reglorl WHO 4 quadrams Dwvde Cbsasi Pd ofPaints Firs Attempt Sub dmde regron mm 4 quadrum 3 Obsvade Imposxit e m mm N4 pom m gash price was Pair of Points Mgomr nm M rhwwmcul mm L 9 mm rougmy gm pmmx on mgh sum Claim Pair of Poinh Algernhm Dmde crow ver cat Mme L so mm roughis an puma an cam 162 1 1 Cant find blosm paw mmdw side marsm Clam Pair of Point Mgsm wm swag rm vammt mm L so mm mughwn yum an each std c r nd mam pm in much 5m rechswaiy cm nd 10st m whh am pornrin mm mg Wimm litmrn hm oi a solufious and mm paw Wm one pow m Each swdz mg m an a Clans Pair bf Palm Claus Pair cf Palm and c osest paw Wm one pow m each sxdz mu m an a Observmm my mud To mdzr pm ms wnhm hf hm L Closed Pair nf Palms Fmddoszs paw wnh one pow m each swdzl ammo m Munl Observmm W Med 390 consider pmms wi m 5 of m L 30m poms m 255mm mm y coovdh vmz Clasnst Pair nf Points Fmddoszsr paw wnh one pow m each sgtd21mmvhn duruml Obslr39vmm onPy md to armer pmms mm 5 of m L garv pmms m 26 57mm mm y coordmaz y Ow check disarm of these WWI llpvsmms m sorfsd Us Clans Pair of Poinh w L2 3 b2 mg pow m m 2mm WW1 The M smastr yr39coor dmatz dawn If1212 h2nth2 dvsvuncz bszzen s and s m mm a Pf No me poms be m sml rbyr box Two points m mm 2 rows 0pm have d smnoez 2amp5 2mm Facv sum mm m we mm 12 wnh7 alum Pair Algorin ow Log n 27m z 061 01quot be 1 Claus Pair of Points Analysis Runmnghmz Q Can wa acmzvz om og n A V25 Don t sorrpomrs m 91m from scravch Each hmz Eadw mm Na Mum W10 hm 2N pom 5mm byy coordmate and an poms sorted by x coordmme Sort by mm mm pawsorted ms Algorithm Design and Analysis 1 f1 Fi 3 gt LECTURE 27 A m Network Flow w E 39 Appllcatlon Bipartite Matching Adam Smith 10222008 A Smith based on slides by S Raskhodnikova and K Wayne Recently FordFulkerson 0 Find maX st ow amp min st cut in 0mnC time All capacities are integers S C We will discuss how to remove this assumption 0 Duality Max ow value min cut capacity Integrality if capacities are integers then FF algorithm produces an integral maX ow 10222008 A Smith based on Slides by S Raskhodnikova and K Wayne Last time Reductions Project Selection Problem Section 711 Reduction of proj ect selection to mincut Today Maximum bipartite matching Reducing MBM to max ow Hall s theorem 10222008 A Smith based on Slides by S Raskhodnikova and K Wayne MaTching MaTching InpuT undirecTed graph G V E M Q E is a maTching if each node appears in cn mosT edge in M Max maTching find a max cardinaliTy maTching Bipar ri re MaTching BiparTiTe maTching InpuT undirecTed biparTiTe graph G L U R E M Q E is a maTching if each node appears in cn mosT edge in M Max maTching find a max cardinaliTy maTching mafching 1239 3139 4539 Bipar ri re MaTching BiparTiTe maTching InpuT undirecTed biparTiTe graph G L U R E M Q E is a maTching if each node appears in cn mosT edge in M Max maTching find a max cardinaliTy maTching gtlt Qquot C I max mafching 1 13922393339 4439 33 0 9 O 3 ReducTions Roughly Problem A reduces To problem B if There is a simple algoriThm for A ThaT uses an algoriThm for problem B as a subrouTine Usually Given insTance x of problem A we find a insTance x39 of problem B Solve x39 Use The soluTion To build a soluTion To x Useful skill quickly idenTifying problems where exisTing soluTions may be applied Good programmers do This all The Time Reducing BiparTiTe MaTching To Maximum Flow Reduction To Max flow Cr39eaTe digraph G39 L U R U s T E39 Dir39ecT all edges from L To R and assign capaciTy 1 Add source s and capaciTy 1 edges from 3 To each node in L Add sink T and capaciTy 1 edges from each node in R To T Bipar ri re MaTching Proof of CorrecTness Theorem Max cardinaliTy maTching in G value of max flow in 639 Proof We need Two sTaTemenTs max maTching in G S max flow in G max maTching in G 2 max flow in G Bipar ri re MaTching Proof of CorrecTness Theorem Max car39dinaliTy maTching in G value of max flow in G39 Pf s Given max maTching M of car39dinaliTy k Consider flow 1 ThaT sends 1 uniT along each of k paThs f is a flow and has car39dinaliTy k Bipar ri re Matching Proof of Correc rness Theorem Max cardinali ry ma rching in G value of max flow in G39 Pf 2 LeT f be a max flow in G39 of value k In regrali ry Theorem gt k is in regral a capaci ries are 1 gt 1 is 01 Consider M se r of edges from L To R wi rh fe 1 each node in L and R par ricipa res in of mosT one edge in M IMI k consider cu r LU s R U T Exercises Give an example where The greedy algoriThm for MBM fails How bad can The greedy algoriThm be ie how far can The size of The maximum maTching global max be from The size of The greedy maTching local max WhaT do augmenTing paThs look like in This maxflow insTance Perfec r MaTching Def A maTching M Q E is perfecT if each node appears in exachy one edge in M Q When does a biparTiTe graph have a perfecT maTching STrucTure of biparTiTe graphs wiTh perfecT maTchings Clearly we musT have ILI IRI WhaT oTher condiTions are necessary WhaT conditions are sufficienT Per fec r MaTching NoTaTion LeT S be a subseT of nodes and IeT NS be The seT of nodes adjacent To nodes in S ObservaTion If a bipar39TiTe graph G L U R E has a per39feCT maTching Then IN 2 ISI for all subseTs S Q L Pf Each node in S has To be maTched To a differem node in NS No perfecf mafching S 2 4 5 N5 239 539 Marriage Theorem Marriage Theorem Frobenius 1917 Hall 1935 LeT G L U R E be a biparTiTe graph wiTh ILI IRI Then G has a perfecT maTching iff INS 2 ISI for all subseTs S Q L Pf gt This was The previous observaTion No perfecf maTching S 2 4 5 N5 239 539 Proof of Marriage Theorem Pf lt Suppose 6 does noT have a perfecT moTching For muloTe as a max flow problem wiTh oo consTr39oinTs on edges from L To R and let A B be min cuT in 639 By maxflow mincut copA B lt L I Choose 5 L D A copAB IL BIIR A Since min cuT con39T use 00 edges NS Q R D A IN5Is IR AI copABL B lt LL B ISI D s 24 5 L B13 RnA239539 K NS239539 Bipar ri re MaTching Running Time Which max flow algoriThm To use for biparTiTe maTching Generic augmenting paTh Om vaf Omn CapaciTy scaling Om2 log C Omz ShorTesT augmenTing paTh Om n1 2 NonbiparTiTe maTching STrucTure of nonbiparTiTe graphs is more complicaTed buT wellundersTood TuTTeBerge EdmondsGalai Blossom algoriThm On4 Edmonds 1965 BesT known Om n12 MicaIiVazirani 1980 Recently beTTer algoriThms for dense graphs eg On238 Harvey Algorithm Design and Analysis u m Computational 39 m LECTURE 37 m Classes P and NP NPcornpleteness Sofya Raskhodnikova m l Review Question FACTORING factor a given integer Question Give a related decision problem Reminder Decision problem X is a set of strings Instance strin s Algorithm A solves problem X As yes iff s e X Answer PRIMES X 2 3 5 7 11 13 17 23 29 31 37 Polynomial Time Algorithm A runs in polynomial time if for every input string 5 As terminates in at most ps quotstepsquot ulnere p is some polynomial length efs PRIMES has a polynomial time algorithm AgrawaIKayaISaxena 002 NM Isla Definition of Class P r Decision problems for which there is apolyetime algorithm l r n Gradesclwul rilvlslarl MULTIPLE st emultipleot y RELPRIME Arexeneyrelenyelypmmea EuclldlSDUEEQ at 39 M 51 Plumes st prime AKS znnz so 51 Elsire Is the edit eisrense between Dynarn io nrerner 2cm DISTANCE Xand yle ss men a pmgra nmlng nenher tttgta lstnere eyeeterxinet seussgemones a t i t t v n t OWE smlsflzsAx elimination ll ng Lil l j Definition of Class NP Certification algorithm intuition Certifier views things from manager lal Wlewpolm Certifier doesn t determine whether s e X on its own rather it checks a proposed proof t that s e X Def Algorithm Cs t is a certifier for problem X if for every string s s e X i there exists a string t such that Cs t yes certificate er Witness NP Decision problems for which there BXlSiS a polyrtlme certifier Cs t is u pulyrtlme ageritnm and ltl sptlsl fer seme pulynumlcll pt Remark NP stands for nondeterministic polynomialetime Certifiers and Certificates Composite COMPOSUES given an integer s is s compositev Certificate A nontrivial factor t of 5 Note that such acertificate exists iff sis composite Moreover ltl s lsl Certifier boolean soniposltesCertlflerts t l Jf ltst ortzsl recurn false else Jf is is 2 multiple of cl return true else return false gt Instance s 437669 Certificate t 541 or 309 43766954lgtlt 309 Conclusion COMPOSITES is in NP Certifiers and Certificates 35atisfiability SAT etyeh aCNF tormuta so ts there a sattstythg asstg mz t Certtftcate Ah asstghmeht of truth vaiues to the Vi booteatt yartabtes Certttter Check that each ciause tho has at teast ohe true hterat EX szyvmamvgvaMoqvayayx v v instances Ktt FK Q 1 certi catet Cohctustott SAT ts M NP Certifiers and Certificates Hamiltonian Cycle HAMVCVCLE etyeh ah uhdtrected graph 5 v E does there extst a stthpte cycie c that ytstts eyery hodev Certtttcate A pertttutattoh of the h hodes Certttter Check that the pertttutattoh cohtaths each hode th v exactty ohce ahd that there ts an edge betweeh each patr ot adJacem hodes th e permutattoh Cohctustott HAMVCVCLE ts Vi NP thstattee s certi cate t P NP EXP P beetstoh probteths tor whtch there ts atttt Vt tttht EXP beetstohprobteths tor whtch the e ts ah t a tt utttt te ah atgortthth that ruhs th ttthe 02PUSD for some potyhothtat p beetstoh probteths tor whtch there ts an a N39tu u that ctatttt P NP Pt Cohstder ahy probteth gtlt th P By defttttttott there extsts apoiyritmz atgortthttt As that soives gtlt Certtttcate t 5 certttter Cs t Ats Ciatm NP g EXP Pt Cohstder arty probteth x th NP By detthtttoh there extsts apoiyrttme certttter Cs t tor x To sotye thput s run s t oh att strthgs t wtth ttt s pisi Return yes ttcts t returhs yes tor ahy ot these The Main Question P Versus NP Does P NPgt tCooh197tErtthohdsLeytttyabtohshtaodet Is the dectstoh probteth as easy as the certtttcattoh probiem Ciayl thttttohprtze If P NP If P NP W t Peak RSA etyptugraphy aha putenttcuiy cuiiapse eeuhuthy It yes Etttcteht atgortthths tor 37COLOR TSP FACTOR SAT It ho No etttcteht atgortthths posstbte tor SPCOLOR TSP SAT Cohsehsus opthtoh oh P NPgt Probabty ho NPCamplete NPrcompiete A probteth v th NPrcompiete tt V is m NP x spy v for eyery probteth gtlt th NP Theorem Suppose v ts ah NPrcompiete probteth Thth ts sotyabte th poiyrttme tttP NP t P NP thth can be sotyed th poiyrttme sthce v ts th NP Let x be any propteth th NP Sthce gtlt lt v we cah sotye x th imp poiyrttme Thts tthpttes NP P We aiready know P g NP Thus P NP F 4 1 be there t t haturat Circuit Satisfiability CIRCUUVSAT etyeh a combthattohat ctrcutt buttt out of ANDOR and NOT gates ts there away to set the ctrcutt thputs so that the output ts 17 uutput The quotFirstquot NPComplele Problem Pf Atty algorithm that takes attxed number of bits h as input and produces ayesho answer can be represented by such a ctrcutt Moreover tt atgortthtn takes polyrttme theh ctrcutt ts ot polyestze Theorem CIRCUITVSATtsNPrcomplete Cookl97lLeyth lQ73 tsketch sketchy part at praat hxtng the number at btts ts trnpar ant and reflects baslc dlst nctlun between algurlthms and clrcults Consider some problem x tn NP It has a polyrtttwe certtttercts t To determtne whether s ts th x need to know tt there extsts a certtttcate t ot length plsl such that Cs t yes e Cs t as an algortthtn on lsl t plslblts tnput s certtttcate t and convert it into apotyestze ctrcutt K e ttrst lsl btts are hardecoded thh s e rematntng plslbtts represent btts ot t Ctt cutt K ts sattsttable tttcts t yes Example Ex Construction below creates a circuit K whose inputs can be set so that K outputs true ttt graph 6 has an thdepehdeht set of stze 2 tndependent set of size 2 tndependent set a bath end utnts uf sume ed e have been shngew 9 0 0 a 2 hardrcuded tnputs graph descrtpttan n tnputs nudes tn tndependent set set at stze 2gt washes Establishing NPCompleteness Rem Once we establtsh ttrst natural Npecomplete problem others tall ltke domtnoes Rectpe to estabttsh NPrcompleteness of problem v Step1 ShowthatVtstVl Step 2 Choose an NPrcomplete problem X Step 3 Prove that X spy Justtttcattoh It x ts ah NPrcomplete problem and v ts aprobtetn th NP With the property that X 3wa v thehv ts NPecotnptete Pt LetW be any problem th NP Then w spy x g By trahstttytty W SP K P in b Hence v ts NPrcomplete k w mmquot mm quot ecarnptete 3SAT is NPComp lele Theorem 3VSAT ts NPrcomplete Pf Sufftces to show that CIRCUUVSATSP 3VSAT SlYtCE 3VSAT ts lYt NP Let K be any ctrcutt Create aaesat yartable x tor each ctrcutt element t Make ctrcutt compute correct yalues at each node e x2 2 x3 2 add 2 clauses msz ex xgyxs 2 add a clauses we spy gym 15 ex exsz 2 add a clauses gm gm may output gtltn Hardecoded tnput yalues and outputyalue ex5o 2 addictause e X X2 exam 2 add 1 clause a Final step turn clauses ot length lt a tnto x5 x x n s s clauses of length exactly a by addthg extra yartatttes x y gtlt2 ts sattsttabte tff x vxz vy1cv1c2 v y is sattsflabte NPCompleteness obseryatton All problems below are Npecomplete and polynomtal reduce thh Karp reducttons to one anotherl by dehntttan at NPrcumpleteness ovaMama 39 swimsuit on some SCHEDULle Some NPComplete Problems to t Packing problems sUePAcKINeJNbEPENDENT SET Covering problems SETecoyERMERTExecoyER Constraint satisfaction problems SAT aesAT Sequencing problem HAMILTONIANecycLETrayettttg Salesman Partitioning problem beMATcHINe aecotok Numerical problems suBsEiesuM KNAPSACK Practice ivlost NP problems are either known to be in P or NPcomplete For most search problems if the corresponding decision problem is in P the search problem can be solved in polynomial time Notable exceptions Decision problem39 Graph isomorphism ch problems Factoring Nash equilibrium Extent and Impact of NPCompleteness Extent of NPecomptetehess Papadtmttrtau 1995 Prtmz thtetteetuat export of cs to other dtsetphhes 0000 cttattahs per year MHZ abstract keywords e more than comptter aperatthg system database sctehttsts had beeh asptrthg to compute teastbty H Npeeomptetehess eah gutde setehttttc mqmr y 192a Ismg thtroduees stmpte modet for phase trahsttmhs 1944 ohsager sotves 2D case th tour d2 force 19gtltgtlt Feynman aha other top mmds seehab sotutmh 2000 1stratt proves ab probtem Npecomptete More Hard Computational Problems Aeru pace engmeer mg aattmat mesh aarttttahthg fur tthtte etemehte 1quot Q a Chemteat engmeer mg heat exchanger hetwarhsyhtheets ctttt engmeer mg equthbrtum uf urban tram aw c y Ehvtruhmehtat engmeer mg upttmat ptaeemeht ufeuhtamthahtsehsurs Fthahetat engmeer mg tth mthtmum rtskpurtfuhu atgweh returh 5ame Maury ttha Nash equthbrtum that maxtmtzes saetat wetrare e Operahnns research aattmat resuurce attaeattah Phyetee aarttttah tuhettah uf 37D 13mg maaet th etattetteat meehamee Puhhcs Shaptzyrshubtkvutmgpuwer up cuHure ts quotCy stattsttes upttmat expertmehtat aestgh Mmeweeper eahs te Algorithm Design and Analysis E LECTURE 18 gm Dynamic Programming i 5 4 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 an2ixiyi Eix Eiyi b2iyi a2ixi 2 2 n ixi Eixi n lt 001 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 1515 Segmented Least Squares Algorithm INPUT n p1pN I c Segmented Least Squares MO O for j 1 to n for i 1 to j compute the least square error ei the segment p1 pj j for minlsisj eij 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 a not the x AB I BD yzBDCAB BCBA LCSx y gt gt 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 a not the BCAB LCSOC y 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 Motivation 0 Approximate string matching Levenshtein 1966 7 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 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 555 Recursive formulation CU j Z ci 1j 1 1 ifxz39 y39 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 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 of Z is an LCS of a pre x ofx and a pre x Ofy 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 Recursion tree m 7 n 6 x x m l 7919 l g l J I Height m n gt work potentially exponential 1062008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9 5 Recursion tree 0 m7n6 439 2 H 1 same I 0 a V subproblem 39 r l l l mln 1 I 5 T E 7 ii r L C 39 Virgil VI Jquot q 715 43quot r 7 1 Vlk r 39 39 quot i V 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 D namic r0 rammin y p g g 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 cij NIL then ifxi y 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 Dynamicprogramming IDEA A B C B D A B Compute the O O O O O O O 0 table bottomup B 0 0 1 1 1 1 1 1 D 0 0 1 1 1 2 2 2 C O O 1 2 2 2 2 2 A 0 1 1 2 2 2 3 3 B 0 1 2 2 3 3 3 4 A 0 1 2 2 3 3 4 4 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Dynamicprogramming IDEA A B C B D A B Compute the O O O O O O O 0 table bottomup B 0 0 1 1 1 1 1 1 Time mquot D 0 0 1 1 1 2 2 2 C O O 1 2 2 2 2 2 A O 1 1 2 2 2 3 3 B O 1 2 2 3 3 3 4 A O 1 2 2 3 3 4 4 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne o o Dynamlcprogrammlng IDEA Compute the table bottomup B Time mn Reconstruct LCS by tracing backwards NNNr r OO B A NNh dP dt Kt Kow A 0 1 2 2 3 3 4 wwNNr Ar Aow AUJNNr AO OOOOOOO F F r OOOO WWNNNr O A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne o o Dynamlcprogrammlng IDEA Compute the table bottomup Time mn Reconstruct LCS by tracing backwards Multiple solutions are possible 1062008 NNNr r OO A 0 0 0 0 l l l NNr Ar Ar tl tow wwNNNr OU A 0 l 2 2 3 3 4 AUJNNr Aow wwNNr Ar Aow OOOOOOO gtwgtOUw A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne o o Dynamlcprogrammlng IDEA Compute the table bottomup B Time mn Reconstruct LCS by tracing backwards Space mn B KT book Ominm n A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne NNNr r OO NNr dr dt Kt Kow A 0 1 2 2 3 3 4 wwNNr Ar Aow AUJNNr AO P P P OOOO OOOOOOO WWNNNr AO Algorithm Design and Analysis Dynamic Programming hortest Paths m LECTURES 23 AND 24 g Sofya Raskhodnikova w Shortest Paths Shortest path prabtam etyan a dtrzctzd graph 5 v E thh adga t watghts c th shortest path from nada s to nada uHawmgmm Mtghts Ex Nodes raprasant agents tn attnanctat satttng and cw ts cost of transactton tn whtch wa buy tram aganty and satt tmmadtataty to w l t m t n A an Q n 15 x A an a M shortest Paths Failed Attempts buhstra Can fatt tf there are nagattva adga costs shortest Paths Negative Cast Cycles Nagattya cost octa obsaryatton It soma path from s to t contatns a nagattya cost cycta there does not agtlttst a shortest set path otherwtsa thara axtsts one that ts stmpta atvv a o shortest Paths Dynamic Programming bat 0PTtt v tangth at shartastyet path P usmg at most t adgas t tt no such path axtsts Case 1 P asas utmost hl adgas e OPTtv OPTthw Casa 2 P usas axactty t adgas e tt y w ts ttrst adga than OPT usas y w and than satacts bast wet path ustng at most tel edges 0 1 10 0pm min0PTirly y m gamma waw athemse tune s R marh By przvtous observatton tt no nagattya cyctas than OPTO PI y tangth at shortest yet pat shortest Paths Implementation ShortestrPathtG H t roxaash nasta v E v 0 v mo 1 F o for a 1 ca n71 faxaash node v s v mu v mua v forezch astga tv at s E MD v v Ilun t MD v M171 w e CW Anatysts etmn ttma etne spaca Fmdmg tha shortest paths Mamtam a successor for aach tabta W shortest Paths Improvements Mammm only one array MM shortzs w path tharwz have found so far No need to check edges of H12 form v w unizss Mw changed m przwous llzr aho Theorem anougnom mg algorwhm MM ls zngm of some v4 path and after rounds of updates m2 value Mv ls no larger Man m2 zngm of shorrzsr v4 path usmg g edges Overall nnpam Mzm 39 cry 0m n Running Mme 0mn worst case but subsmmwaHy fasrzr m practice BellmanFord Efficient Implementation EAJmaanoId4horcgstrEatblG s n foreach node v E V L Mvl suocossorm 9 q o 71 1 w E v c Jf mm has been updated n pmuous itoramom v w E E sucdessoIN w gt If no Mm value changed in iteration 3 stop gl Example of BellmanFord The demanslranan 8 for a sngnymerem version afme algarnhm see 0mg mm campules melances from mesaurse node ramer man melances 0 We deslmauan node gl Example of BellmanFord Initialization gl Example of BellmanFord Order of edge relaxation 2 l Example of BellmanFord 2 l Example of BellmanFord End of pass 1 I Example of BellmanFord l Example of BellmanFord End of pass 2 and 3 and 4 minLth W Distance Vector Protocol Communtcatton network Nodes routzrs Edges dtrect communtcatton WM Cost of Edgz u may 0 tmu mtumttvmqmwcmaunwm mva bukstra s atgorttnm Requtres gtobat tnformatton of network BeHmattrFord Uses ontv tocat knowtzdge ot netgnbortng nodes svncnrontzatton We don t expect routers to run tn tockstzp The order tn wntcn each foreach toop executes tn not tmportant Moreover atgorttnm stttt converges even tt updates are asynchronous Distance Vector Protocol Distance vector protoc Each rou maintains avector of shortest path lengths to eve other node dlslanczs and the tirst hop on each path directions Algorithm each rout r pe forms n separate computations one for each potential destination no Routing by rumor eroxXNS RIP Novell s IPX RIP Cisco s IERP DEC s DNA Phase 1v AppleTalRls RTMP Caveat Edge costs may i during algorithm or tail completely i 39 iseunnng m intimtyi 2 i dnlnad Detecting Negative Cycles Lemma If omnv OPTtlrlv for all v then no negative cycles are connected to l Pf BellmaneFord algorithm Lemma It OPTtivlt opitnelv tor some node v then any shortest path from v to t contains acycle Moreover W has negative cost Pf by contradiction since OPTnv c OPTOHN we Rnow P has exactly n edges By pigeonhole principle p must contain a directed cycle w Deleting w yields avsl path with c n edges 2 W has negative cost CW c o Detecting Negative Cycles Application Currency conversion eiven n currencies and exchange rates between pairs of currencies is there an arbitrage opporlumly RemarR Fastest algorithm very valuablei a 17 I m 3IEI 2 3 2 ma llnnnn mi 5o Bun Path Vector Protocols LinR state routing nativsttnvistmunutitstnvp E c router also stores the entire path Based on Dleslr u s algorith m Avolds Coutllltlgrlorltlfltllly problem and related ditticulties Requires significantly more stora Ex Border eateway Protocol BGP Open shortest Path Flr sl OSPF Detecting Negative Cycles Theorem Can detect negative cost cycle in 0nin time Add new node t and connect all nodes to t with Oscosl edge ChecR it own v OPTUH v tor all nodes v e ityes then no negative cycles 7 it no then extract cycle from shortest path tromv to t Detecting Negative Cycles Summary Bellmaanord 0mtl time 0m n space BellmaneFord tor n iterations instead ot nel Upon termin ation Bellmaanord successor variables trace anegative cycle it one BXlSlS 4 tor improved version and early termination rule Algorithm Design and Analysis 1 f1 E LECTURE 28 I Network Flow 1 i 5 v Choosing good augmenting paths Capacity scaling algorithm A Smith A Smith based on slides by K Wayne and S Raskhodnikova 11142008 Prebreak FordFulkerson 0 Find maX st ow amp min st cut in 0mnC time All capacities are integers S C Today removing this assumption 0 Duality Max ow value min cut capacity Integrality if capacities are integers then FF algorithm produces an integral maX ow 10 22 2008 A Smith based on Slides by S Raskhodnikova and K Wayne Residual Graph Original edge e u v E E COPGCW Flow fe capacity ce 17 6 flow Residual edge quotUndoquot flow sent e u v and eR v u Residual capacity Q 11 j ce fe if e e E 6 cfe fe if eR E E residual capacity residual capacity Residual graph 6f 2 V E Residual edges with positive residual capacity Ef e 1 fe lt ce U eR ce gt O FordFulkerson Summary FordFulkerson While you can Greedin push flow UpdaTe residual graph Theorem FF algori rhm Termina res wi rh a maximum flow Two big ideas a Max flow 3 min cu r b ValueFF oquuT flow capaciTysome cuT Hence FF flow is maximal and The corresponding cu r is minimal original ne rwork Proof of b f flow ou rpu r by FF algori rhm A seT of ver rices reachable from s in residual graph 61 Lemma valuef capaci ryA see LecTure 22 FordFulker39son Exponen rial Number of Augmen ra rions Q Is generic FordFulker39son algoriThm polynomial in inpuT size m n and log C A No If max capaciTy is C Then algoriThm can Take C iTer39aTions 1 118 0 11a 01 c c c c 11221 133t1lto c c C 0 V x11 10 quot 1amp1 Choosing Good Augmen ring PaThs Use care when selecTing augmenfing paThs Some choices lead To exponenTial algor39ifhms Clever choices lead To polynomial algor39ifhms If capaciTies ar39e ir39r39afional algor39iThm noT guar39anTeed To Terminafe Goal choose augmenfing paThs so That Can find augmenting pafhs efficienfly Few iTer39aTions Choose augmenfing paThs wifh EdmondsKar39p 1972 DiniTz 1970 Max boTTleneck capacify Sufficienfly lar39ge boTTleneck capacify Fewesf number39 of edges CapaciTy Scaling InTuiTion Choosing paTh wiTh highesT boTTleneck capaciTy increases flow by max possible amounT Don39T wor39r39y abouT finding exacT highesT boTTleneck paTh MainTain scaling parameTer39 A LeT Gf A be The subgraph of The residual graph consisTing of only ar39cs wiTh capaciTy cn leasT A 110 102 110 102 lt1gtltlt 12g ltlgt170 1 6 f 22 170 of 100 Capaci ry Scaling Scaling Max FlowG s t c foreach e E E fe e 0 A t smallest power of 2 greater than or equal to C Gf residual graph While A z 1 GfA t A residual graph while there exists augmenting path P in GfA f t augmentf c P augment flow by z A update GfA Alt A2 return f CapaciTy Scaling Cor r ec rness AssumpTion All edge capaciTies ar39e inTeger39s beTween 1 and C InTegr aliTy invar39ianT All flow and residual capaciTy values are inTegr39al Cor39r39ecTness If The algor39iThm Ter39minaTes Then 1 is a max flow Pf By inTegr39aliTy invar39ianT when A 1 gt GfA Gf Upon Ter39minaTion of A 1 phase There are no augmenTing paThs CapaciTy Scaling Running Time Lemma 1 The ouTer while loop repeaTs 1 log2 C Times Pf IniTially C s A lt 2C A decreases by a facTor of 2 each iTeraTion Lemma 2 LeT f be The flow aT The end of a Ascaling phase Then The value of The maximum flow f is aT mosT vf m A1 proof on nex r slide SaniTy check vf vf s mA and A shrinks so vf converges Towards vf Lemma 3 There are aT mosT 2m augmenTaTions per scaling phase LeT f be The flow aT The end of The previous scaling phase Lemma 2 2 vf s vf m 2A Each augmenTaTion in a Aphase increases vf by aT leasT A Theorem The scaling maxflow algoriThm finds a max flow in Om log C augmenTaTions IT can be implemenTed To run in Om2 log C Time Why CapaciTy Scaling Running Time Lemma 2 LeT f be The flow aT The end of a Ascaling phase Then value of The maximum flow is aT mosT vf m A Pf almosT idenTicaI To proof of maxflow mincuT Theorem We show ThaT aT The end of a Aphase There exisTs a cuT A B such ThaT capA B s vf m A Choose A To be The seT of nodes reachable from s in GfA By definiTion of A s E A By definiTion of f T 6E A vf Ef e E fe eoutoA eintoA 2 2 ce A 2 A eoutofA eintoA 2 ce 2 A 2A eoutofA eoutofA eintoA 2 capAB mA original neTwork So vfvf s capAB vf 2 mA BesT Known AlgoriThms For Max Flow Reminder The scaling maxflow algoriThm runs in Om2 log C Time Currenle There are algoriThms ThaT run in Time Omn log n On3 Ominn23 m12m log n log C AcTive Topic of research Flow algoriThms for specific Types of graphs Special cases biparTiTe maTching eTc MuITicommodiTy flow Algorithm Destgn and Analysts Review Question Exponentiation Problem Compute a b where b E Nis n bits long Question How many multiplications m LECTURE 11 Naive algorithm b 92 exponential Solving Recurrences in the input length Master Theorem Divideandconquer algorithm b a x a if b is even a 111 4 2 x WHY2 x a if b is odd Sofya Raskhodnikova Tb Tb2 1 2 Tb log b n W M So far 2 recurrences The master method Mergesort Counting Inversions Tn 2 Tn2 n n log n The master method applies to recurrences of Binary Search Exponentiation the form Tn 1 Tn2 91 log n Tn aTnb fn where a 2 1 b gt 1 andf is asymptotically Master Theorem method for solving recurrences positive that isfn gt0 for all n gt no mm mm Three common cases E Th ree common cases Compare fn with ubgbquot Compare fn with ubgbquot 1 fn 0n10gba 5 for some constant e gt O 1 fn 0n10gb 5 for some constant e gt O fn grows polynomially slower than nmbquot fn grows polynomially slower than nmbquot by an n8 factor by an n8 factor Solution Tn nk gba Solution Tn nk gba 2 fn nk gba lgkn for some constant k 2 O fn and nmbquot grow at similar rates Solution Tn nk gba lgktln mm m Three common cases cont Compare fn with WEI 3 fn Rumba 5 for some constant e gt O fn grows polynomially faster than ubgbquot by an n8 factor and u satisfies the regularity condition that afnb S cfn for some constant c lt 1 Solution Tn fn mm m Idea of master theorem Recursion tree mgta fnbgt fnbgt fnbgt a fquotb2gt fquotb2gt fnb2gt Til W Idea of master theorem Recursion tree WgWWWWNgt MM Mgtw meMMgt a fnb2 fltnb2gt fltnb2gt Til mm W l Idea of master theorem Recursion tree ogwwwwmgt NM mgtm m mwwgt a h logbn fnb2 fltnb2gt fnb2quotquotquotquotquotquotquotquotquot3902fnb2 Til W l Idea of master theorem Recursion tree WgWWWWNgt M fnb fnb fnbquotquotquot39quotquotafnb hlogbn a fnb2 fnb2 fnb202fquotb2 leaves 2 oh log nlogbaf1gt mm a ml Idea of master theorem Recursion tree WgWWWWNgt NM Mgtm mwmegt a h logbn fltnb2gt fltnxb2gt fltnxb2gta2fltnxb2gt CASE 1 The Weight mcrwses E geometrically from the root to the TO laves The lmves hold a constant quot ubgbquot TU fraction of the total Weight 0110ng am l Idea of master theorem Recurxi0ntree quot fnb fnb fnbquotquotquotquotquot39afquotb hlogbn l gta fnb2 fnb2 fnb2 T1 quotn1 gb T1 nk gbalg n W wl Examples Ex Tn 4Tn2 n a 4 b 2 D n1 gba n2fn n CASE 1fn 0012 s for e 1 Tn nz mm Examples E EX Tn 4Tn2 n3 a 4 b 2 D n1 gba n2fn n3 CASE 3fn 2022 8 for e 1 and 40123 S 013 reg 00nd for c 12 Tn 013 mm m l Idea of master theorem Recursion tree quot fquotb fquotb fquotbquotquot quot nb h Iogw M fnb2 fnb2 fnb2 39 39 39 39 39 02fquotb2 5 CASE 3 The weight decrwses I I quot nk gbquot T1 fctron of the total Welght V Examples Ex Tn 4Tn2 n a 4 b 2 2 n1 gba n2fn n CASE 1fn 0012 for e 1 Tn nz Ex Tn 4Tn2 n2 a b 2 D n1 gba n2fn 1 CASE 2 fn n21g0n that is k 0 Tn nzlg n mmnm Examples E EX Tn 4Tn2 n3 a 4b22n1 gb n2f nn3 CASE 3fn 2022 8 for e 1 and 40123 S 013 reg 00nd for c 12 Tn 013 EX Tn 4Tn2 n2lgn a 4 b 2 3 quot10ng n2fn nZlgn Master method does not apply In particular for every constant e gt O we have n8 c0lgn mmnm Algorithm Design and Analysis Approximation Algorithms Load Balancing m LECTURES 39 40 m3 Sofya Raskhodnikova Approximation Algorithms Q Suppose I need io soive an NPrhard probiem whai shouid 1 dov A Theory says you re uniiheiy io find apoiyriime aigoriihm Musi sacrifice one of ihree desired feaiuresi Soive probiem in poiyriime Soive arbiir ary insiances of ihe probiem oapproximaiion algoriihm uara iorunin poiyriime aranieed io soive arbiirary insiance of ihe probiem Guaranieed io find soiuiion Wiihin raiio p ofirue opiimum Em chaiienge Need io prove a soiuiiori s vaiue is ciose io opiimum Wiihoui even hnoWing whai opiimum vaiue isi Load Balancing Problem Inpui in ideniicai machines YlJObSJ0bJ has processing iime iJ JobJ in run coniiguousiy on one machine A machine can process ai mosi OYlBJOb ai aiime Def Lei Jii be ihe subsei ofJobs assigned io machine i The ioad of machine i is L 21 E m 1 Def The mahespan is ihe maximum load on any machine L max L 600i Assign each Job io a machine io minimize mahespan Load Balancing Llsl Scheduling Lisirscheduiirig aigoriihm o ider mobs in some fixed or der AssigViJobJ io machine whose ioad is smaiiesi so far List Schadulingm n cl2 ex 1 l to m Ll o iouohnvnnchimi m 4 g k labsmgncnmhhu in j gt 1 to n i mumink 1k machinihnsenninsiinc 111 a 411 u j assignnbgimchn i L1 1 t k uydunioudoimuchinoi i xacuxn Implemeniaiion 0n log n iime using a prioriiy queue Load Balancing Llsl Scheduling I m Isl Machine 1 Machine 2 Machine 3 illl Time Load Balancing Llsl Scheduling a u e H Machine 2 Machine 3 Time ill Load Balancing List Scheduling I marlin JAMM 31 Time 3 a in Load Balancing List Scheduling I Mcc rli39r ml Mach 2 JAMM 31 Time l Load Balancing List Scheduling a I I M MI L Mmle 2 ligating 3 Time l Load Balancing List Scheduling II lg n trial Mach 2 E H ligating 3 Time l Load Balancing List Scheduling s I I Manhunt 1 Math ll Time Load Balancing List Scheduling I Load Balancing List Scheduling llili Time Load Balancing List Scheduling Load Balancing List Scheduling E quotL E Time Load Balancing List Scheduling Load Balancing List Scheduling Analysis Theorem Bralmm lgo o Greedy algorithm is a 2eapproXiination worstecase analysis ot an approxlmallon algorithm Need to compare resulting solution With optimal makzspan L Lemmal The optimal mahespati L 2 maxi t1 Pf Some machine riiust process the riiost timeeconsuminggob Lemmaz The optimal mahespan L2iz t m J J Pf The total processing time is J ii of m machines must do at least a UN traction of total work Load Balancing List Scheduling Analysis Theorem Greedy algorithm is a2eapproXirnation Pf Consider load L ot bottleneck machine i LetJ b2 laleob scheduled on machine i w engobiassignedtomachine iihadsrnollest load Itsload betore assignment lSL r J s Lk fovalll ksmi bmnwbsschndulnd bdmnl Load Balancin 39 Lisi Scheduling Analysis Theorem ereedy algoriihm is a2eapproXimaiion nei E a 0 ET 1 3 3 me i i had smallesl load Ils load rl 2 L elJ g Lk loralllghgm Load Balancing Lisi Scheduling Analysis Q Is our analysis lighlv A Essenlially yes Ex m machines mlmemobs lenglh lJobs oneJob of lenglh m iisi senmuiing malaspan IV Load Balancing Lisi Scheduling Analysis Q Is our analysis lighlv A Essenlially yes Ex m machines mlmemobs lenglh lJobs oneJob ol lenglh m opiimai manspan in Load Balancing LPT kule Longesl processing lime LPT SON VlJobs in descending order of processing lime and lhen run lisl scheduling algorilhm Mm Edl umifl 11 1112 4 Im jabs 0 sin e a earn z e in 391 I 1 to l zlo a Mammal m P g wagndlnmehwl fax 3 1 Eu n t x a x ncainaihusndww am o m u m a mcgngahgmaaehimi Lib 141 c cmadeloadairrmchni xntuxn w Load Balancing LPT kule obseryalion If al mosl in Jobs lhen lislescheduling is oplimal Pl Each Job pul on ils own machine Lemma3 Il ihere are more lhan in Jobs L 2 2 lm pl Consider lirsl m1 Jobs l W Since lhe ly s are in descending order each lakes al leasl lw lime There are m Jobs and m machines so by pigeonhole principle al leasl one machine gels lWOJ l Theorem LPT rule is a32 approxlmallon algorilhm l Same basic approach as for lisl sche u ing LI L rzj t a u 3 ltEL M N quot 6 Lemma 3 by absecyalicin can assume number maps gt m Load Balancing LPT kule Q Is our 32 analysis lighlv A No Theorem 6rdham1969 LPT rule is a 43rappr oxlmall0n Pf More sophislicaled analysis of same algorilhm Is Graham s 43 analysis lighlv A Essenlially yes Ex m machines n 2mllJobs 2J0bs of each lenglh mll ml2 2mei and oanob ol lenglh m Load Balancing State of the Art Load Ba ancmg c Nprcompxm even for 2 machmzs Browse Prove mg smrzmzm Hw v0 prove NPrhardnzss reduce from the proMzm m Exzrmsz 26 m Chapvzr E Po ynomwa Tm Approxwmanon Scheme PTAS 1 cyapprox manon algomhm for any constant cgt Load ba ancmg Hochbaumrshmovs 1987 Consequence pus produces arbnrar y mgh quamy somnon but mm m accuracy for Mme Algorithm Design and Analysis LECTURE 1 m Analysis of Algorithms Course information Why study algorithms Stable matching problem Sofya Raskhodnikova m Course information 1 Staff 6 Syllabus 2 Course website 7 Homework 3 Prerequisites 8 Grading policy 4 Lectures 9 Collaboration policy 5 Textbook 10 Exams and grading g Course Objectives classical algorithms analysis of algorithms standard design techniques 3 Etymology of Algorithm Aba Abdallah Muhammad ibn Musa al Khwarizmi c 780 850 AD Persian astronomer and mathematician lived in Baghdad father of algebra On calculating with hindu numerals rwtise in Arabic 825 Algoritmi de numero lndorum translation into Latin 12th century author s name mistaken fora plural noun mme to mean mlculation methods N Algorithm Design and Analysis Theoretical study of how to solve computational problems sorting a list of numbers finding a shortest route on a map scheduling when to work on homework lg Performance Typical goal Find most space andtimeefficient algorithm for given problem What else is important 7 modularity 7 userfriendliness 7 correctness Programmer time 7 maintainability SimpliCity 7 functionality 7 extensibility 7 robustness 7 reliability Performance is the currency of computing 3 Why study algorithms a hmguage for talking about program behavior standard set of algorithms and design techniques fwsibility What an and mnnot be done 7 halting problem NPrcompleteness analyzing correctness and resource usage successful companies Google Mapquest Akamai computation is fundamental to understanding the World 7 cells brains social networks physical sysmms all can be viewed as computational devices ITIS FUN m Matching Residents to Hospitals Goal Given a set of preferences among hospitals and mediml school students design a selfreinforcing admissions process Unstable pair applicant x and hospital y are unstable if r x prefers y to its assigned hospital and r y prefers x to one of its admitmd students Stable assignment no unstable pairs 7 Individual selfrinterest Will prevent any applicanthospital deal from being made Algerithm Design and Analysis m LECTURE 7 Greedy Algorithms cont d Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9102008 Review 0 In a DFS tree of an undirected graph can there be an edge uv Where v is an ancestor of u back edge where v is a sibling of u cross edge Same questions With a directed graph Same questions With a BFS tree directed undirected 9102008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Interval Scheduling Problem Job j starts at sj and nishes at Two jobs are compatible if they do not overlap Find maximum subset of mutually compatible jobs a b g a g h 0 l 2 3 4 5 6 7 8 9 10 11 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Time 9102008 Greedy Counterexamples for39 earlies r starT Time for shortest interval for fewest conflicts 9102008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Formulating Algorithm Arrays of start and nishing times SI 82 Sn f1 f2 fn 0 Input length 2n 6n 9102008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Greedy Algorithm Earliest nish time ascending order of Sort jobs by finish times so that f1 5 f2 5 s fn A A Set of selected jobs for j 1 to n if job j compatible with A Alt AUj return A 01mplementation On log n time 0n space Remember job j that was added last to A Job j is compatible with A if sj 2 9102008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Sort jobs by finish times so that f1 5 f2 5 s fn 1 A empty A Queue of selected jobs j lt 0 for j 1 to n if fW lt s n X 01 3 J enqueuej onto A return A 9102008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Analysis Greedy Stays Ahead Theorem Greedy algorithm is optimal Proof strategy by contradiction Suppose greedy is not optimal Consider an optimal strategy which one 0 Consider the optimal strategy that agrees with the greedy strategy for as many initial jobs as possible Look at rst place in list where optimal strategy differs from greedy strategy Show a new optimal strategy that agrees more w greedy 9102008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Consider lectures in increasing order of start time assign lecture to any compatible classroom Sort intervals by starting time so that s1 5 s2 5 5 sn d 0 A Number of allocated classrooms for j 1 to n if lecture j is compatible with some classroom k schedule lecture j in classroom k else allocate a new classroom d 1 schedule lecture j in classroom d 1 d s d 1 Implementation On log n time On space For each classroom maintain the nish time of the last job added Keep the classrooms in a priority queue main loop n logd time 9102008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Analysis Structural Argument Observation Greedy algorithm never schedules two incompatible lectures in the same classroom Theorem Greedy algorithm is optimal Proofz Let d number of classrooms allocated by greedy Classroom d is opened because we needed to schedule a lecture say j that is incompatible with all d1 last lectures in other classrooms These d lectures each end after sj Since we sorted by start time they start no later than sj Thus we have d lectures overlapping at time sj e Key observation gt all schedules use 2 d classrooms 9102008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Scheduling to minimize lateness 9102008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne Scheduling To Minimizing LaTeness Minimizing laTeness problem Single resource processes one job aT a Time Job j requires TJ uniTs of processing Time and is due aT Time dj Ifj sTarTs aT Time s iT finishes aT Time fJ sJ TJ LaTeness Q max 0 fj dJ Goal schedule all jobs To minimize maximum laTeness L max 3 1 5 Ex I tj 3 2 1 4 3 2 68991415 lateness 2 lateness O max lateness 6 l l l d39 d28 d615 d16 d514 d49 1 2 3 4 5 6 7 8 9 1O 11 12 13 14 15 Minimizing La reness Greedy Algor i rhms Gr39eedy Templa re Consider jobs in some order Shor39TesT processing Time fir39sT Consider39 jobs in ascending order of processing Time TJ Ear39lies l39 deadline fir39sT Consider39 jobs in ascending order of deadline dJ SmallesT slack Consider39 jobs in ascending order of slack dJ TJ Minimizing La reness Greedy Algor39i rhms Gr39eedy Templa re Consider jobs in some order Shor res r processing Time fir39sT Consider39 jobs in ascending order of processing Time TJ tj 1 10 counterexample SmallesT slack Consider39 jobs in ascending order of slack dJ TJ j counterexample Algorithm Design and Analysis Tractability m LECTURES 38 39 Extending the Limits of m5 Finding Small Vertex Covers Solving NPhard Graph Problems on Trees Sofya Raskhodnikova Coping With NPCoriipleteriess Q Suppose I need to solve an Neecomplete problem what should 1 dov A Theory says you re unlikely to tind polyetime algorithm Must sacritice one ot three desired teatures Solve problem to optlmalltv Solve problem in polynom al time Solve arbitrary instances ot the problem This lecture Solve some special cases ot Neecomplete problems that arise in practice Finding Small Vertex Covers Vertex Cover A vertex cover of a graph 6 v E is a subset of vertices s g v such that for each edge u v either u e s or v e s or both Problem Given a graph 5 v E and an integer k find uveriex cover of size S k if it exists k4 S36710 Finding Small Vertex Covers Q What if llt is small7 Brute torce Oth nm Try all Ctl e otnt subsets ot size h Tahes 00m time to chech whether asubset is avertex cover Goal Limit exponential dependency on b e g to 02k n Ex n 1000 k 10 Brute force knk 1103 2 infeasible Better 2k n 10A 2 feasible Remark If h is a constant algorithm is polyrtlmz39 it h is a small constant then lt S also practical Important The algorithm is still exponential and hence scales badly e g consider h40 However it is better than brute torce Finding Small Vertex Covers Clalml Let ueu be an edge ot e s has avertex cover otsize g llt itt at least one ot e etu ands em has avertex cover ot size g bet delete v and all incident edges Pt 2 as avertex cover 5 of SlZe S k S contains either u or v or both WL06 assume it contains u s i avertexcoverof r u t e Suppose s is avertex cover 0H5 etu ot size s bet Then 5 L101 is avertex cover 0H5 Finding Small Vzrfzx Covers Algorifhm Claim 2 The tollowtng algortthm ttnd ayertex cover at stze s x tn 6 tt lt exlsts and runs ln 02k n tlme Swall VClG lot i a my Jf it comm nb cdqea return 9 else return 31 lac in st be any edge on 3 music mi ml 1f 54 4 use return 5 U111 scv saunas 7 mt bit If 5 s false return so u m else return use Pf Correctness follows from Clalm 1 nodes m We recurslotl quot2239 each MVOCGHOH lakes 0t39l ttme Solving NPHar d Graph Problems on Trees Finding Small Vzrfzx Covers Recursion Tree an ifk0 p member ism 3quot My T01 k Independent Set on Trees Independent set on trees elven a tree find a maximum SUbSBl of nodes Such that no We share an edge cardtnaltty Fat 2 on at least lWO nodes has at least two leat nodes degree l Key observatlon va ls a leaf there exlsts a m lmum slze independent set containing y Pf exchange argument nstder a max cardtnaltty tndependent set 5 Itye s were done It u e s andv e s then s u y ts tndependent 2 s not maxtmum IFUE s andye s then s u vru ts tndependent Independent Set on Trees Greedy Algorithm Theorem The tollowtng greedy algortthm ttnds amaxtmum cardtnaltty tndependent set tn forests and hence trees IndnpanmntvSetrIHJLvVonast tel t S wmla I hats at least we adv i Let a in v be an was man max v is a lea 5 l mum s u madam new en El Pf Correctness tollows tram the preytous xey observallon Remarx Can tmplement tn 0tl ttme by constdertng nodes tn postorder ensures a nude ts ytstted after all tts chtldren Weighted Independent Set on Trees Weighted independent set on trees Given a tree and n ode weights wv gt0 find an independent set S that maximizes 2M WV observation If u v is an edge such that v is a leaf node then either OPT includes u or it includes all leaf nodes incident to u Dynamic programming solution Mark some node r as the root 0va u max weight independent set of subtree rooted at u containing u OPTmu max weight independent set of subtree rooted at u not containing u W a u il I ME ma a mum Independent Set on Tnees Algorithm Tneoretn Th2 dynamtc programmtng atgorttntn ttnds atnaxttnutn wetgnted tndependent set tn trees tn otn tttne muwms cn b n main m an at an I a mat x tuxIch and u a 139 in Button 1 tan um I shn 4 lm u 2 15quot Him o M 3153 r250 nude on mtsdza av setticrwt quota I 39 lnmdwm Hmquot V mm s Emmett nuts em um n mums Mm Exerctse ecover tne tndependent set of maxttnutn wetgnt by tractng back Pf Takes otn tttne stnce we utstt nodes tn postorder and exatntne eacn edge exac y once Context Independent set on trees Tnts structured spectat case ts tractabte because we can ttnd anode that I t at ttt WM JH at atnong tne subprobtettts tn dttterent subtrees it see cnnpter w 4 erapns ot bounded tree wtdtn Etegant generattzatton ot trees tnat Ca res a rtcn ctass ot graphs tnat artsz tn practtce Enabtes decomposttton tnto tndependent pteces Algorithm Design and Analysis m LECTURES 29 and 30 Network Flow Application Bipartite Matching Sofya Raskhodnikova Matching Matching Input undirccicd graph 5 M E is a matching ifzach nadc appears in at most cdgc in M Max matching fin ainax cardinaiiiy matching Bipartita Matching Bipariiic matching Input undirccicd bipariiic graph 5 u R E M E is ainaiching it cach nadc appears in at most cdgc inM Max matching fin ainax cardinaiiiy inaichin maic rig hi 172 31 45 Bipartitc Matching Bipariiiz maichiri Input undirccicdbipariiicgraphs u E M E is a matching it cach nadc appears in at most cdgc in M Max in iching fin ainax cardinaiiiy inaichin max matching 1713272 44 Bipartitc Matching Max ow tarnaiaiian Crzaizdigraph Lu usi E rain L to R and assign capacity rc s arid capacity 1 2dgzs f 1ar infinity mm s to cach nadz in L Add sinR i and capacity 1 edges from each nadc i R to eiyzri Carisi Bipartita Matching Proof of Correctness Theorem Max cardinaiiiy matching m6 yaiac of max ow in 5 Pf S inax matching M of cardi aiiiy dzr ow hai sc f is af R s 1 unit aiang cach of Rpaihs ow and has cardinaiiiy Bipartite Matching Proof of Correctness Theorem Max cardinaiiiy maichmg m e vaiue of max ow in 6 Pf 2 Lei f be amax ow in 6 of vaiue h Imegrahiyihzorem 2 his imegrai aiieapaeiiiesare l fisoei Consider M sei of edges from L io R Wiih fe 1 7 each mode M L and R pariicipaies Vi ai mosi one edge M M e M h consider cm LL13 Rut Perfect Matching Def A maiehmgM gE is if each mode appears in exaciiy one edge in M Q When does a bipariiie graph have a perfeei maichmgv Simciure of bipariiie graphs Wiih perfeci maichmgs Cizariy wemusihave iLi iPi Whai oiher condiiiohs are heeessaryv whai commons are suffimemv Perfect Matching Noiaiioh Lei s be asubszi of modes arid iei NS be ihe sei of modes adJGCBN io nodes M S observaiioh 1f abipariiie graph 5 e L u R E has a perfeei maiehmg iheh iNsi 2 isi for aii subseis s g L Pf Each mode in s has io be maiehed io adifferem mode in NS 5424 5 M5 4215 ii Marriage Theorem Marriage Theorem Frobznius i917 HaH i935 Lei e L U R E be a bipariiie graph Wiih iLi iPi Theme has aperfeci maiehmg iff mm 2 isi for aHsubszis s gL Pf 2 This was ihe previous observaiioh 412415 Mg225 i Proof of Marriage Theorem Pf c Suppose s does moi have aperfeei maiehmg Formuiaie as a max ow probiem Wiih oo eohsiraims oh edges from L io R arid iei A B be mm em m 5 By maxefiow mii ircui capA Blt i Li ChooseSLnA capAB iLnBiiPnAi SMCB mm cui cam i use edges NS RnA NLA ROA capABrLnB lt iLiriLnBi iSi q 542457 LnKeU R nA 239 5 MS I 2 aquot Bipariiie Matching Puhhihg Time which max fiow aigoriihm io use for biparme mavchmgv semeric augmzmmg paih 0m vaif 0mh Capamiy scahmg 0m2 iog c 0m2 shoriesi abgmemiimg paih 0m mVZ Nonrbipar iiiz maich n Simciure of nonrbipar iiiz graphs is more compiicaied bui weihumdersiood TqurBzrgzEdmondsr aiqi Biossom aigoriihm ow Edmond51965 Besi hmowm 0m YVVZ Micahrvazir ani JQEO Algorithm Design and Analysis LECTURE 2 3 An Example Problem Stable matching problem Sofya Raskhodnikova Stable Matching Problem Goal Given n men and n women find a quotsuitablequot matching 7Participants rate members of opposim sex 7Each man lists Women in order of preference from best to Worst 7Each Woman lists men in order of preference from best to Worst w t mm us mm lust mm I l Xuvt gr Zeus ctm Vunczy Zeus awe x39mi yamy Zeus Mm mrmm mm Womenr m rmm m M Review Questions In terms of n whatis the length of the input to the Stable Matching problem ie the number of entries in the tables Answer 2n2 What is a simple lower bound on the running time of any algorithm for Stable Matching Answer 2 n The algorithm needs that much time to print the output a Stable Matching Problem Perfect matching 7 Each man gets exactly one Woman 7 Each Woman gets exactly one man Stability no incentive for some pair of participants to undermine assignment by joint action 7 In matching M an unmatched pair m7w is unstable if man I and woman w prefer each other to their current partners 7 Unstable pair m7w could each improve by eloping Stable matching perfect matching with no unstable pairs Problem Given the preference lists of n men and n women find a stable matching if one exists g Stable Matching Problem Q Is assignment XC YB ZA stable mm hast mm mm hast mm l l Clui e Xam Zeus Clare Mm mrmm Pm 0 Women rmm mot g Stable Matching Problem Q Is assignment XC YB ZA stable A No Bertha and Xavier will hook up Mm hast Mm mm hast um i l metre Clare Mm mrmm mm Womenr m rmm m M Stable Matching Problem Q Is assignment XA YB ZC stable am has am has am I I I Bertha Clare A More Kmy Beam Mm mfgm Pm m Women A m rmm I m k Stable Matching Problem Q Is assignment XA YB ZC stable 39 A Yes Xand Y got their first choice Z is the last choise for every woman No man can participate in an unstable pair Mm has Mm am has um I I I I Berma Clare AW 4 ere Berma Womeni m rum m w Mm mrmm mm Existence of Stable Matching Q Do stable matchings always exist A Not obvious a priori a Stable Roommate Problem Stable roommate problem 72n people each person ranks others from 1 to 2n1 iAssign roommate pairs so that no unstable pairs F 3 2 Man 3 C b A7354 2 Humming M C A D was DAVEunsmhle We K a D A4187 2 Humane Doofus A B 5 Observation Stable matchings do not always exist for stable roommate problem g ProposeandReject Algorithm LBJ Proposeand reject algorithm GaleShapley 1962 IthlaJJz em person to be nee quothue same man is free and hasn t proposed to evezy woman i Cheese such a wax in quotI m woman on m39s list to whom III has not yet proposed 3 w 5 free asslqn m and w to be engaged else Jf m prezers m to her Danb m39 assign an and w to be engagea and w co be free else w rejects m Proof of Correctness Termination Claim Algorithm terminates after at most n2 iterations of while loop Pf Each time through the loop a man proposes to a new woman There are only n2 possible proposals nun nx v 2 v v w w x x y y z 2ltNe gt39lt ltN An mm W no1 I lprapasuls rlquvld Algorithm Design and Analysis Randomized Algorithms Contention Resolution Global MinCut Linearity of Expectation not covered in class Sofya Raskhodnikova m LECTURE 42 g Randomization Atgortthrntc destgn patterns ereedv o tvtderandrconquer Randomtzatton tn practtce access ta a pseudurrandum number generatur Randomtzatton Allow tatr cotn tttp tn untt ttrne Whv randorntzev Can tead to strnptest tastest or ontv known atgortthrn tor a parttcutar probtern vmme Ex 5 try breaktng protocots graph atgortthrns qutcksort hashtng toad batanct h ng Monte Carto tntegratton crvptograp v 131 Contention Resolution Contention kesolution in a Distributed System Contentton resotutton 6tven n processes P Pn each cornpettng for access to a shared database It two or more processes access the database strnuttaneoustv att processes are toched out Devtse protocot to ensure att processes get through on aregutar basts Restrtctton Processes can t communtcate chattenge Need symmetryrbreaktng paradtgrn Contention kesolution kundomized Protocol Protocot Each process requests access to the database at ttrne t wtth probabttttv p 1n Ctatm Let St t event that process t succeeds tn accesstng the atabase at ttme it Then le n PrSt t l2n Pt Bv tndependence Prst t p 1epy4 nune at remaining n71 process t requests access processes request access Setttng p 1n we have Prst t 1n 1 e 1nr4 vatue that maximizes Pr5t 0 between 1e ana12 Usetut facts from catcutus As n tncreases from 2 the tunctton 1 7 my converges rnonotontcattv from 14 up to 1e 1 e 1nn converges rnonotontcattv from 12 down to 1e ctatrn the probabttttv that process t tatts to access the databa en rounds ts at most 1e After etttt tn rt rounds the probabtttt most trc Pf L t 1throu ht thndepend PrFt t s 1 e 1en choosettent PrFitS17iiml307 Sf Cnoosetie n iic tn nt MFG m lt i quot nquot r e s Contention kesolution Randomized Protocol se tn v ts at e Ft t ev nt that process t tatts to access database tn rounds ence and prevtous ctatrn we have Contention kesolulio 39 kundomized Protocol Ctaim Tho probability that l procossos succood Within 2o n in n rounds is at ioast to 1n Pf Lot Fi event that at ioast ono of tho n procossos taiis to accoss databaso in any of tho rounds 1 thro g PrFz PtiOFimj s iprmm s r417 A El uniun buund proncius siiao Choosing t 2 lon llc ln n lyiolds PrFi Union bound Givenev39enisE E PriOEii s 2 ME to to Global Minimum Cut slobai min cut eiuon a connoctod undiroctod graph 5 v E ind a cut A 3 of minimum cardinality Applications Partitioning itoms in adatabaso idontify clustors of roiatod documonts notworhroiiabiiity notworhdosign circuit dosign TSP soiuors Notnorh flow soiution Replace every odgo uv With two antiparaiioi odgos u v and v u Pichsomo vortox s and computo min srv cut soparating s from oach othor vortox v E v False intuition Global leerLJl lS harder than lel sit cut 132 Global Minimum Cu r Contraction Algorithm Contraction algorithm Karger i995i Pick an go o u v uniformly at random 2 ropiaco u and v by sin io non supzrrnodz w o prosoruo odgos updating ondpoints of u and v to w o hoop paraiioi odgos but doioto selfrloops Ropoat until graph has Jusi two nod os va Rot nd v2 urn tho cut all nodos that woro contractod to form v TR 3 i f3 6 d Contraction Algorithm Ciaim Tho contraction aigorithm roturns amin cut With prob 2 2n2 Pf Considor agiobai minrcui A 3 of 6 Lot F bo odgos With ono ondpoint in A and tho othor in 3 Lot k iFi sizo o min cut n first stop aigorithm contracts an odgo in F probability 3 lEl Every nodo has dogroo 2 h sinco othorniso A 3 would not bo minrcui 2 lEl 2 ghn Thus aigorithm contracts an odgo in F With probabiiitys 2n Contraction Algorithm Ciaim Tho contraction algorithm roturns amin cut With prob 2 2n2 Pf Considor agiobai minrcui A 3 of 6 Lot F bo odgos With ono ondpoint in A and tho othor in 3 Lot k iFi sizo of min cut 5i bo graph afier itorations Thoro aro yi no supornodos F has boon contractod Tho minrcui in 6 is still it sinco uaiuo of minrcui is h lE 2 glm Thus aigorithm contracts an odgo in F With probability g 2ni Lot El ovont that an odgo in F is not contractod in lizr allot iJ FrE 01320 2 1mm x PtEZ lE I gtlt gtlt HUSH lEmEZunEuI 2 1Tgt1T gtquot1T1T T7305 a m o Contraction Algorithm Ampiitication To ampiity the probabiiity of success run the contraction aigoriihm many times and output the best cut found iaim If we repeat the contraction aigorithm n2 in n times With independent random choices the probabiiity of taiiing to find the giobai minrcui is at most in2 Pf By independence the probabiiity of taiiure is at most iin i i go t 7 my 512 2 nil Global Min Cut Context Best known deterministic Nagamochirlbai aki1992Omn n2 iog n emarh Our aigorithm is siow since we perform etn2 iog n iterations and each takes sum time Improvement Kai39gzrrSiziti i996 0n2 iog3ri Eariy iterations are iess rishy than iater ones probabiiity of contracting an edge in min cut hits 5o a when n v Run contraction aigorithm untii n V2 n d 5 re 2 nodes PZNOM main Run contraction aigorithm s on resuiting graph and return best of two CLHS Extensions Naturaiiy generahzes to handie positiye weights Best known Karger 2000 0m iog3ri faster than best known max ow aigorithm or deterministic giobai mm cut aigorithm 133 Linearity of Expectation Expectation Expectation 6iyen adiscrete randam yariabies x its expectation Egtlt is defined by c 1 HP 11 a Waiting for atirst success Com is heads With probabihty p and taiis with probabihty 17p How many independent ips x untii first headsv EU il FfXJI 1 P4P 1 i11 P yo yo em yhuiis in Expectation Two Properties Usetui property If x is 00 random yariabie Egtlt Prgtlt 1 s i W Em EJ P XJI ZJ PYXJI W41 F0 M no meson human Linearity of expectation eiyen two random yariabies Xarid V detined oyer the same probabihty space Egtlt y Egtlt Em nri a compiex caicuiation into simoier pieces Guessing Cards Game Shuf e a deck of n cards turn them over one at a time try to guess each card i c c i i been turned over aiready Guess a card from NH deck uniformiy at dam The expected number of correct guesses is l Pf tsurprisingiy ettortiess using imearity ot expectation Let 1 if im prediction is correct and O otherWise etgtlte umberofcorrectguessesgtlt Xn Egtlt PPX 11YV EX EPA t o EM lrit oin 1 I imntyot xpmaton Guessing Cards 6am Shuf z a dzck of n cards mm thzm over onz a1 a Mme try to guess cacn card sucssng nun memory sucss acard umform y a random from cards no yzv szzn dam The expected number of cow ch gucsscs1s emog n w 121 x 1 1f 1 prcd1cnon1s correct and o om L21 X number of corrzcv guzsszs x gtlt Egtlt 2rw1s2 Egtlt Egtlt Em lno o 12 11 Hn 1mm Xpmuon 1nno1ann 1 1n n Coupon Collector Coupon co11cc1or Eocn box of ccrco1con1o1ns a coupon There a d1ff2r2m 1ypcs of coupons Assummg 01 ex s are cquoHy hwy 1o comam cocn coupon now many boxcs before you noyc 21 coupon 01 each 1yp2gt dam The expected number of steps 15 en1og n w PhaseJ mnc bevwzzm andJol d1snnc1 coupons 121 x numbcr of s1cps you spcnd1n phaszJ L21 gtlt number of svzps M 101111 gtltn x s X H M n ma 2 Eur1 2 w new n nHn c1 1 W as nun WWW mnngnnnn1 Algorithm Design and Analysis LECTURE 41 Approximation Algorithms The Pricing Method VerteX Cover Sofya Raskhodnikova 1272007 S Raskhodnikova based on slides by K Wayne Weighted Vertex Cover Weighted vertex cover Given a graph 6 with vertex weights find a vertex cover of minimum weight weight 2 2 48 weight 2911 Pricing Method Idea Each edge must be covered by some vertex Edge e pays price pg 2 O to get covered Fairness Edges incident to vertex i should pay S wi in total for each vertex i 2 pg S w eltijgt Fairness Lemma For any vertex cover 5 and any fair prices pg 28 p8 S wS Proof 2 pe S 2 Zpe S Zwi eeE ieS eij ieS each edge e covered by sum fairness inequalities at least one node in S for each node in S Pricing Method Pricing method Set prices and find vertex cover simultaneously Weighted Vertex COVer ApproxGVE w foreach e in E pe lt 0 foreach v in V fofaL W I I totalv O 1 while Hedge ij such that neither i nor j is tight select such an edge e give pe maximum increase without violating fairness increase 6 maxwi totaliwj total pe pe increase totali totali increase totalj totalj increase S e set of all tight nodes return S Pricing Method Figure 118 Pricing Method Analysis Theorem Pricing method gives a 2approximation Pf Algorithm terminates since at least one new node becomes tight after each iteration of while loop Let S set of a tight nodes upon termination of algorithm 5 is a vertex cover if some edge iJ is uncovered then neither i norJ is tight But then while loop would not terminate Let 5 be an optimal vertex cover We show wS S 2wS wS Zwi Z Zpe S 2 Zpe 22196 S 2wS ie s ie s eij ie V eij ee E I I fairness lemma all nodes in S are tight 5 g V each edge counted twice prices 2 0 Running time Om Weighted Vertex Cover Theorem zappmx manon a gorwhm for wzwghrzd vertex cover Theorem bmungafva 2001 If P NP then no papproxwma on for plt1360722n wnh um wzwghrs 10 5 r 21 Open research prob zm 0032 m gap Algorithm Design and Analysis LECTURE 3 m An Example Problem Stable matching problem Asymptotic Notation 0 2 9 o conotation Sofya Raskhodnikova m ProposeandReject Algorithm Observation 1 Men propose to women in decreasing order of preference Observation 2 Once a woman is matched she never becomes unmatched she only quottrades up m Review Question Brute force algorithm an algorithm that checks every possible solution In terms of n whatis the running time for the brute force algorithm for Stable Matching Problem Assume your algorithm goes over all possible perfect matchings Answer Sn Proof of Correctness Perfection Claim All men and women get matched Proof by contradiction 7Suppose for sake of contradiction some guy sa Zeus is not matched upon termination of algorithm 7Then some woman say Amy is not matched upon termination 7By Observation 2 Amy was never proposed to 7But Zeus proposes to everyone since he ends up unmatched W Proof of Correctness Stability Claim No unstable pairs Proof by contradiction 7 Suppose AZ is an unstable pair they prefer wch other to their partners in GaleShapley matching S 7 Case I Z never proposed to A WWW WWW 2 Z prefers his GS partner to A quotquot 39 Pquotquotquotquot gt AZ is stable 7 Case 2 Z proposed to A 2 A rejected Z right away or later gt A prefers her GS partner to Z 7 WM anmmd up gt AZ is sta le g Efficient Implementation We describe 0n1 time implementation Assume men have le n and so do women Engagements data structures 7 a list of free men eg a queue 7 two arrays wife In and husband w set entry to D ifunmatched tfm matchedtu w men w re m w and husband w 7m Men proposing data structures 7 an array men7pref m1 13911women on m3911 list 7 an array count In how many proposals m made m Efficient Implementation Women rejectingaccepting data structures 7 Does woman w prefer man in to man 139 7 7 For each woman create inverse of preference list of men 7 Constant time queries afmr 0n preprocessing per woman Amyprefersman 3 m a 5m mmm wusqu 2 7 or 1 1 to n inversemref j J m Summary Stable matching problem Given n men and n women and their preferences find a stable matching if one exists GaleShapley algorithm Guarantees to find a stable matching for every problem instance Time and space complexity 0n2 linear in the input size W Asymptotic Order of Growth Upper bound T n is 0fn if there exist constants c gt O and n0 2 0 such that for all n 2 no OSTM Sc fn Lower bound T n is Sfn if there exist constants c gt O and n0 2 0 such that for all n 2 no Tn Z c fn Tight bound Tn is fn if Tn is both Ofn and 9f Example Tn 32n2 17n 32 7 Tn is 0n2 0n3 9n2 9n and n2 r Tn is not 0n 9n3 n or n3 W Notation Onesided equality Tn Ofn iNot transitive fn 5n3 gn 3n2 39 fn 0n3 gm but fn gn iAlternative notation Tn e Ofn Meaningless Any comparisonbased sorting algorithm requires at least On log n comparisons iUse S for lower bounds g Properties Transitivity 71f f 0g and g 0h then f 0h 71f r 9g and g 9h then r not 71f f g and g h then f h Additivity 71f f 0h and g 0h then r g 0h 71f r not and g 9h then r g 9h 71f f h and g 0h then f g h w Common Functions Asymptotic Bounds Polynomials a0 an adnd is nd if ad gt O Polynomial time Running time is 0nd for some constant d independent of the input size n Loga thms loga n T logb n for all constants a b gt O m 7 WW h 5 ing W5 Salim w my wimmmi For every x gt 0 log n 0nquot w mmm W5 5 W W paw Exponentials For all r gt1 and all d gt 0 nd 0r Factorial By Sterling s formula n 260mg Overview m Some functions sorted by g as m totic rowth Iogltngt HM quot1000000 2 beats nk for any fixed k 39n Algorithm Design and Analysis Network Flow Choosing good augmenting paths Capacity scaling algorithm m LECTURES 27 3 Sofya Raskhodnikova mm FordFulkerson Exponential Number of Augmentations Q Is generic Forderuiherson aigorithm poiynomiai in input sizev 39 m n mid ing a A No It max capacity is C then aigorithm can take C iterations in u in ii c c c c llil gt lt igtuxii C 5 C 5 ii mi in mi Choosing eooa Augmenting Paths Use care when seiecting augmenting paths Some choices iead to exponentiai aigorithms Cieyer choices iead to poiynomiai aigorithms If capacities are irrationai atgorithni not guaranteed to terminatei soai choose augmenting paths so that Can tind augmenting paths etticientiy FEW HBV GHOHS Choose augmenting paths with Edmondsexarp 1972 binitz 1970 Max botttenech capacit Sufficientiy iarge bottienech capacity Fewest number of e ges Capacity Scaling Intuition Choosing path with highest botttenech capacity increases ow by max possibie amount Don t worry about tinding exact highest bottienech path Maintain scahng parameter Let 5pm be the subgraph ot the residuai graph consisting ot oniy arcs with capacity at teast A nu iu2 nu iu2 gt3 gt3 122 nu i22 nu a 5mn Capacity Scaling Scallhngaer Joth s t ct t foreach e e E rtei e o A sinanest power of 2 greater than or equal to c at P re 1dua graph WhJJ A 2 J i at At kr sldual graph nhne tthere exists augmtjnq path 2 1n sxtAtt t f augnienttf c 2i upstate ctAt gt A t A 2 gt return f Capacity Scaling Correctness Assumption Aii edge capacities are integers between 1 and C Integraiity invariam Aii tiow and residuai capacity yaiues are integrai Correctness It the aigorithm terminates thent is a max tiow rt By integraiity invariant when A 1 2 6A 6 Upon termination otA iphase there are no augmenting paths Capacity Scaling Running Time Capacity Scaling Running Time Lem 1 The autzr whttz taap repeats 1 o H0926 tth L2mma2 Let t be thz ow at thz 2nd of aArscahng phase Thzhyatuz Pf IhtttaHy c Alt 2c A damasas by a factor of 2 aach ttaratton of tha maxtmam ow ts at most t o m A Pf atmost tdehttcat to proof at maxr ow mmrcut thaor 39 We show that at tha 2n of aArphasa theta axtsts acat A B such that capA B s vf m A Choose A to be tha sat of hodas raachabta from s tn 64A By dattnttton of A s E By dattnttton of t t a A 2mma2 Lat t be tha ow at tha 2nd at aArscahng phasa Than tha yataa at tha maxtmum ow v ts at most vf m A mummt Lzmmaa Thzrz arz at most 2m augmzhtattohs pzr scatthg phasz Lat f be tha ow at tha 2nd at tha przvtous cahng phasa L2mma2 2 ym g yttm 2A Each aagmantatmn muArphasz tnmasasytt by at taastA Vm 2 m 7 2 m We Theorem Th2 scattng maxr ow atgortthm hnds amax ow m 0m tag 6 2 2 LatehA 7 2 A augmentahons Itcanbatmptamantadtomntnotmztogc tt 2 7 2 C 7 2 A 2A g cm A 2 MPHB rm anghat netwark Best Known Algorithms For Max Flow Rzmmdzr Th2 scattng maxr ow atgortthm runs tn ottn2 tag 6 tth Currzhtty thzrz arz atgortthms that mm m tth y 0mn tog n 3 y n y Ommn23 mm m tog n tag 6 Algorithm Design and Analysis LECTURE 14 Divide and Conquer Fast Fourier Transform Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 9242008 Midterm Exam 1 Willard Building Room 76 Tuesday night September 30 815pm You may bring one 1 doublesided handwritten 85 X 11 sheet of notes on colored paper Hint use its preparation as a study aid 9242008 A Smith based on Slides by E Demaine C Leiserson S Raskhodnikova K Wayne FasT Fourier Transform ApplicaTions ApplicaTions OpTics acousTics quanTum physics TelecommunicaTions conTr39ol sysTems signal processing speech r39ecogniTion daTa compr39ession image processing DVD JPEG MP3 MRI CAT scan Numer39ical soluTions To Poisson39s equaTion The FFT is one of The Tr39uly gr39eaT compuTaTional developmenTs of This 20Th cenTur39y IT has changed The face of Science and engineering so much ThaT iT is noT an exagger39aTion To say ThaT life as we know iT would be very differenT wiThouT The FFT Charles van Loan Fas r Fourier Transform Brief His rory Gauss 1805 1866 Analyzed periodic moTion of asTeroid Ceres RungeK6nig 1924 Laid Theore rical groundwork DanielsonLanczos 1942 Efficient algori rhm CooleyTukey 1965 Moni roring nuclear Tests in Soviet Union and Tracking submarines Rediscovered and popularized FFT ImporTance noT fully realized un ril advent of digi ral compu rers Polynomials Coefficien r Represen ro rion Polynomial coefficien r representation 2 1 Ax a0 alx a2x an1xquot Bx b0 blx b2x2 bn1xquot391 Add On arithmetic operations Ax Bx a0 b0a1b1x an1bn1xquot391 Evoluo re On using Hor39ner39s me rhod Ax a0 xa1xa2 xan2 xan1 Mul riply convolve Onz using brute force 2n 2 I i Axx Bx 2 Ci x where c1 E ajbi i0 i0 Polynomials Poin rValue Represen ra rion Fundamen ral Theorem of algebra Gauss PhD Thesis A degree n polynomial with complex coefficien rs has n complex r39ooTs Corollary A degree n1 polynomial Ax is uniquely specified by its evaluation at n disTincT values of x YJ39 AXJ39 Polynomials Poin rValue Represen ra rion Polynomial poin rvalue r39epr39esen ra rion Ax XosJ o Xn1ayn1 Bx X0 20 Xn1 zn 1 Add On arithmetic operations Ax Bx x0y0 20xn1yn1zn1 Mul l39iply On bu l39 need 2n1 poim s Ax x Bx x0y0 x 20x2n1y2n1x 22H Evalua re Onz using Lagrange39s for39mula H x x j A H x goyk 110 xj jaek Conver ring Be rween Two Polynomial Represen ro rions Tr39odeoff FosT evaluation or39 fast mul riplico rion We won t boTh RepreSenToTion MulTiply CoefficiemL Onz On PoinTvolue On Onz Goal Make all ops fast by efficien rly conver39Ting be rween Two r39epr39esen ro rions a0a1an1 A quotquotxn 1 yn 1 coefficien r poin rvalue represen ra rion represen ra rion Conver ring Be rween Two Polynomial Represenfa rions Bru re For39ce Coefficien r To poin rvalue Given a polynomial a0 a1 x an1 xn39l evaluate if at n distinct points x0 xn1 0n2 for ma rr39ixvec ror39 mul riply 2 71 1 yo 1 x0 x0 x0 a 2 71 1 yl 1 x1 x1 x1 11 2 n l 1 2 quot 1 a 3 yn l xn1 xn1 xn1 n l On for Gaussmn elimina rion Vander39monde ma rr ix is inver rible iff xi dis rinc r Poin rvalue To coefficient Given n distinct points x0 xn1 and values yo yn1 find unique polynomial a0 a1 x an1xquot391 rha r has given values at given poin rs Coefficien r To PointValue Represen ra rion In rui rion Coefficien r To poin rvalue Given a polynomial a0 a1 x an1 xn39l evaluate if at n distinct points x0 xn1 Divide Br39eak polynomial up into even and odd power39s Ax a0 alx azx2 a3x3 a4x4 a5x5 a6x6 a7x7 Aevenx a0 azx a4x2 a6x3 Aodd x a1 a3x a5x2 a7x3 39 X Aevenxz X Aoddxz 39 A39x Aevenxz 39 X Aoddxz In rui rion Choose Two poin rs To be 1 A 1 Aeven1 1 Aodd1 A1 Aeven 1 Aodd1 Can evalua re polynomial of degree 5 n a r 2 points by evaluating Two polynomials of degree 5 n at 1 point Coefficien r To PointValue Represen ra rion In rui rion Coefficien r To poin rvalue Given a polynomial a0 a1 x an1 xn39l evaluate if at n distinct points x0 xn1 Divide Br39eak polynomial up into even and odd powers I 00 01x GZXZ G3X3 G4X4 a5x5 06x6 G7X7 39 Aevenx c O39l39 02X 14X2 06X3 Aodd X 01 03X Cl5x2 a7x3 39 A X Aevenxz X Aoddx2 391 39 AX Aevenxz 39 X Aoddxz In rui rion Choose four39 points To be 1 il 39i A 1 Aeven 1 1 Aodd1 A1 Aeven 1 1 Aodd 1 Can evalua re polynomial of degree 5 n A i Aeven1 i Aodd1 a r 4 poinTs by evaluaTing Two polynomials of de me 5 in at 2 oinTs 39 A39l Aeven391 39 l Aodd391 g 2 p Discre re Fourier Transform Coefficien r To poin rvalue Given a polynomial a0 a1 x an1 xn39l evaluate if at n distinct points x0 xn1 Key idea choose xk 00k where a is principal n rh roof of uni ry yo 1 1 1 1 a0 yl 1 D1 002 03 Du 1 a1 yz 1 D2 04 we om 1 a2 y3 1 03 ms 09 0301 1 a3 yH 1 Dn l w2n 1 D3n 1 O moi 1x114 art 1 l Discre re Fourier Transform Fourier ma rrix Fn Roo rs of Uni ry Def An n rh roof of unify is a complex number x such Tha r x391 1 Fact The n rh roofs of unify are 000 001 on where 00 e 27 i quot pf mkn e 2niknn eni2k 12k 1 Fact The nh roofs of unify are v0 v1 vnZ39l where v e 4 i quot FGC I39 002 v and 002 k vk Fos r Fourier Transform Goal Evoluo re a degree n1 polynomial Ax o0 on1 xquot391 of HS n rh roofs of unity 000 001 on Divide Br39eok polynomial up into even and odd powers 39 Aevenx 00 02X Cl4X2 an22 xn3912 39 Aodd X 01 03x G5X2 an21xn12 39 Ax Aevenxz X AoddX2 Conquer Evoluo re degr39ee Aevenx and Aoddx of The nh roofs of uni l y v0 v1 vnZ39l Combine Aook Aevenvk 00k Aoddvk O s k lt n2 k k 2 kn2 2 MW AVvltkaoddvlt 0skltn2 V m 0 mk39H IZ Dllt FFT Algor39i rhm fft n aoa1 an1 if n 1 return a0 eoe1en21 lt FFTn2 aoa2a4an2 dod1dn21 lt FFTn2 a1a3a5an1 fork0ton2 1 wk lt e2nikn yk lt ek 00quot dk k Ykn2 ek w dk return yo Y1 I IYn l FFT Summary Theorem FFT algori rhm evalua res a degree n1 polynomial at each of The nfh roofs of why in On log n steps assumes n is a power of 2 Running Time T2n 2Tn On 2 Tn On log n On log n L r 0 1 aO alan an l 60 7y09quotquotwn ynl coefficien r poin rvalue r39epr39esen ra rion r39epr39esen ra rion Recursion Tree perfect shufer an r a2 r a4 r as a1 r a3 r a5 r a7 an 1 a4 a2 1 as a1 1 35 a3 1 a7 an 34 32 35 31 35 33 3 7 000 100 010 110 001 101 011 111 quotbi39rreversedquot order Poin rValue To Coefficien r Represen ra rion Inverse DFT Goal Given The values yo yn1 of a degree n1 polynomial at The n poinTs 10 11 0039 find unique polynomial a0 a1 x an1xquot391fhaf has given values at given points 1 a0 1 1 1 1 1 yo a1 1 ml Dz 03 Du 1 yl a2 1 Dz 034 ms 00201 1 yz a3 1 13 16 039 130 y3 61H 1 Du 1 0201 1 0301 1 wn 1n 1 yH l i 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 00 2 0 3 w n l G 1 1 0 2 0 4 0 6 w 2n 1 n n 1 0 3 0 6 0 9 w 3n 1 1 w n I w 2n 1 w 3n 1 I w n 1n 1 Consequence To compute inverse FFT apply same algori rhm but use 00 1 e 392 i quot as principal n39rh roof of unify and divide by n Inverse FFT Proof of Correctness Claim Fn and 6n are inverses Pf F G kk 1 Elm 00 l E1 wk k39j 1 ifkk n n n j0 n 0 otherwise summa rion lemma Summa rion lemma Le r 00 be a principal n rh roof of unify Then nil kj n if k E 0 mod n w i0 0 otherwise Pf If k is a mul riple of n Then 00quot 1 gt sums To n Each n roof of unify 00quot is a roof of x 1x 1 1 x x2 Xn1 if mk 1we have 100k00k200k 10 gt sumsToO Inverse FFT Algorithm ifft n a0 a1 an1 if n 1 return a0 eoe1en21 lt FFTn2 aoa2a4an2 dod1dn21 lt FFTn2 a1a3a5an1 fork0ton2 1 wk lt e Zacikn yk lt ek 0quot dk n Ykn2 ek 39 wk dk n return yo Y1 I r Yn l Inverse FFT Summary Theorem Inverse FFT algor39i rhm in rer39pola res a degree n1 polynomial given values at each of The n rh roofs of unify in On log n sTeps assumes n is a power of 2 On log n 0 1 a0a1an1 A y09 9wn 7yn 1 lt coefficien r 00quot log n poin rvalue r39epr39esen ra rion r39epr39esen ra rion Polynomial Mul riplico rion Theorem Con mul riply Two degr39ee 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 0 19quot 2n 2 b0b1bn1 FFT On log n inver39Se FFT On log n AX0 Ax2n1 poin rvalue mulfiplica rion BX0Bx2n1 om CXoCx1Cx2n1 InTeger MulTiplicaTion InTeger mulTiplicaTion Given Two n biT inTegers a an1 a1ao and b bn1 b1b0compuTe Their producT c a x b ConvoluTion algoriThm 1 Form Two polynomials I Nofe a AZ b Bxbob1xb2x2bn1xn 1 CompuTe Cx Ax x Bx EvaluaTe CZ a x b Running Time On log n complex ariThmeTic sTeps 2 n Ax a0 a1x a2x an1x Theory Schb nhageSTrassen 1971 On log n log log n biT operaTions NlarTin FUrer Penn STaTe 2007 On log n 239 9 biT operaTions PracTice GNU MulTiple Precision AriThmeTic Library 6MP proclaims To be llThe fasTesT bignum library on The planeTquot IT uses bruTe force KaraTsuba and FFT depending on The size of n Algorithm Design and Analysis LECTURES 33 34 Network Flow Applications 0 Project Selection 0 Survey Design 0 Image Segmentation Sofya Raskhodnikova MW 5 Roekhoofnikovo based on slide by K Wayne Application Project Selection can he oosmve or negailve Projects with prerequisites et P of possible projects Project v has associated revenue pv 7 some projects generate money create interactive ecommerce interface redesign web page 7 others cost money upgrade computers get site license Set of prerequisites E If v w e E can39t do project vand unless also do project w A subset of projects A g is feasible if the prerequisite of every project in A also belongs to A Project selection Choose a feasible subset of projects to maximize revenue Project Selection Prerequisite Graph Prerequisite graph e an edge from v to w if can39t do v without also doing w v w x is feasible subset of projects vx is infeasible subset of projects feasible infeasible Project Selection Min Cut Formulation Min cut formulation Assign capacity w to a prerequisite edges Add edge s v with capacity p if pv gt0 Add edge v t with capacity pv if pvlt o For notational convenience define p5 P 0 pH w w m w sltgcltbs h 7 Project Selection Min Cut Formulation Claim A B is min cut iff Aes is optimal set of projects Infinite capacity edges ensure A 4s is feasi e Max revenue because copAB Epv new yes we yen gee Pv EPv Project Selection Restated Open Pit Mining Openpit mining studied since early 1960s Blocks of earth are extracted from surface to retrieve ore Each block v has net value pv value of ore processing cost Can39t remove block v before w or x Application Survey Design Survey design Design suryey asking n consumers about n2 pr d Can oniy survey consumer i about uproduciJ if they o n it een c and c questions one per product A Ask between p1 and p consumers about produciJ eoai besign asuryey tnat meets tnese specs it possibie Bipartite perfect matching Speciai case when 9 Application Image Segmentation Image segmentation Centrai probiem in image pro biyide image into conerent regions cessing Ex Inree peopie standing in front of compiex background scene Identity eacn person as a conerent obJeci Image Segmentation Formuiate as min cut probiem aXimiZaHOVi Nos u rsink Undirected grapn Turn into minimization probiem 2ai2b e 2 MaxtmiZing EA jEBJ WEE imltuii1 equiyaient to minimizing Vai2 V1 7 217 2e e mm s or aiternatiyeiy za1zbf 2P0 yea z EA 0 an Ai iiz JiH 21 eo imi e E 2e imimH Survey Design Aigoriihm Formuiate as a circuiation probiem Witn tower bounds i Inciude an edge H it customer o roduct Integer circuiation i teasibie survey design Image Segmentation Foreground background segmentation Labei eacn pixei in picture as beionging to p 20 is separation penaity for iabeiing on andJ as toreground and tne otner as background eoais Accuracy ifa gt by in isoiation prefer to iabei i in toregr u d Smootnness it many neignbors of i are iabeied toreground we ound snouid be inciined to iabei i as forzg Find artition AB tnatmaXimizes i 7 P I Zal 2b 2 pl furegruund backgraunct IE A JE 8 w E E A t rJ1 Image Segmentation inii eQ Formuiate as min cut probiem 6 v E Pi Add s rce to correspond to foreground g add sink to correspond to background P s se two antieparaiiet edges instead of undirected edge Image Segmentation Consider min cut A B Wl6 A or ound mmAiB 2a12bi 2pm 1223 l EA 01125 is Al 12 B ifi andi un different sides ance Precisely the quantity We Want to minimize p caunted exactly 393 K a r 5 t A bi Application Baseball Elimination Which teams have acnance of finishing the season with most WlYlS7 Montreal eliminated since it can finish With at most E0 Wins but Atlanta already has 83 s W r lt W reteam i eliminated Only reason sports Writers appear to be aWare of Sufficient but not necessaryi Baseball Elimination Atlanta 63 71 B e l 6 l 90 79 a l 39a 2 New tam 7a 78 a 6 o a Mammal W 62 3 l 2 0 Which teams haye achance of finishing the season With most Win37 phiiiy can Win E3 but still eliminated IfAtianta loses agame then some other team Wins one Remark Answer depends nolJusl on iiimi moi games atready Won and left to play but also on tiiii they re against Baseball Elimination Baseball elimination problem S of teams S Distinguished team s E 5 Team x has Won WX games already Teams x and y play each other rxyaddilional times Is there any outcome of the remaining games in Which team s finishes With the most or tied for the most Win37 Baseball Elimination Mm Flow Formulatlon Can team 3 finish with most W As ume team 3 Wins all remaining games a WS e ra Wins biyyy remaining games so that all teams hayeg Wa ra Wins i3 3 a 331 N e o w game nudes team nudes Baseball Elimination Mm Flow Formulation Theorem Team 3 is not eliminated iff magtlt flow saturates all edges ieaying source Integraiity theorem 2 each remaining game betWeen gtlt andy added o umber of Wins for team x or team s Capacity on x t edges ensure no team Wins too many games L2 3 t9 43 W 3 game nodes team nodes Baseball Elimination Explanation for Sports Writers Baseball Elimination Explanation for Sports Writers 28 27 2 Aim Mgus in mi ALEnsl Augusll JWA Which learns have achance of finishing lhe Season Wllh mosl WWlS7 Which learns have achance of finishing The Season Wllh mosl WlYlS7 Dzlr alf could finish season Willi 49 s 27 6 Wins DEN Olf could finish season Willi 49 r 27 76 Wins Cerllflcale of elimination R Nv Bal Bos Tor Have already Won WR 27E games Must Win at least 7 01 2 mo re Average team in R Wins at least ao54gt7o games Baseball Elimination Explanation for Sports Writers Baseball Elimination Explanation for Sports Writers Cerllflcale of ellmlnallon Pf of lheorem eru nm mngam max flow formulallon and consider min cm A B res Wm zwi gm 2a an s 7 Define v ieam nodes on source side afmln cu e lnflnllz capaclly edges ensure lfxry s A inen x e A an y e A e le e A and A but xry e T inen adding xry to A decreases If gtwlgl inenZisiiiiiiiiiii lbysubselT capacllyafcul Theorem HoffmanrRlvlll11967 Team 2 is eliminated lff inere exisis a Subsel T lhal ehmmales Z ream x can still Wininis Proof idea Lel T leam nodes on Source Side of min all games lefl many more games Baseball Elimination Explanation for Sports Writers w of ineorem max hoW formulallan and consider mm cui A B Define v team nodes on source side of min cu Observexry e A in bolh x e v and y e v gSlzl gt PM 3 panacea Bamyacmasuxmy Balavl39ly 7 gSz 10 2Wcgrwx m 7 gSlzlgT WT lT Wcgc Algorithm Design and Analysis Dynamic Programming Knapsack problem RNA Secondary Structure 3 LECTURE 19 e Adam Smith A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 1082008 Review questions ShortestpathGst shortest route from s to 2 LongestpathGst longest simple path from s to 2 Question Do Shortest Path and Longest Path have optimal substructure that can be used for a polytime dynamic programming algorithm What if the graph is a DAG 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Knapsack Problem Given n objects and a quotknapsackquot Item i weighs wi gt O kilograms and has value vi gt O Knapsack has capacity of W kilograms Goal ll knapsack so as to maximize total value Ex 3 4 has value 40 W11 V 0 Many packing problems t this model a 1 1 1 Assigning production jobs to factories Deciding which jobs to do on a single 2 6 2 processor with bounded time 3 18 5 Deciding which problems to do on an exam 4 22 6 5 28 397 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Knapsack Problem Given n objects and a quotknapsackquot Item i weighs wi gt O kilograms and has value vi gt O Knapsack has capacity of W kilograms Goal ll knapsack so as to maximize total value Ex 3 4 has value 40 W11 Greedy repeatedly add item with a maximum ratio v1 wt 6 Example 5 2 1 achieves only value 35 gt greedy not optimal 22 nthIl 2 18 5 6 28 397 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Knapsack Problem Given n objects and a quotknapsackquot Item i weighs wi gt O kilograms and has value vi gt O Knapsack has capacity of W kilograms Goal ll knapsack so as to maximize total value Ex 3 4 has value 40 W 11 Greedy algorithm a 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne w hs Dynamic programming attempt 1 De nitionz OPTi maximum pro t subset of items 1 i Case 1 OPT does not select item i OPT selects best of l 2 il Case 2 OPT selects item i without knowing what other items were selected before i we don39t even know if we have enough room for i Conclusion Need more subproblems 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne FEMALE Adding a new variable De nition OPTi W max pro t subset of items 1 iwith weight limit w Case 1 OPT does not select item i OPT selects best of l 2 il with weight limit w Case 2 OPT selects item i 0 new weight limit w wi OPT selects best of l 2 i l with new weight limit 0 if i 0 0PTiw 0PTi lw if wigtw max0PTi 1w vi 0PTi 1w w otherwise 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne Siamquot I Bottomup algorithm Fi11 up an nbyW array Input n W wlp riv vh for w 0 to W MO w 0 for i 1 to n for w 1 to W if wi gt w Mi w Mi 1 w else Mi w max Mi l w vi Mi l w wiJ return Mn W 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 83 5amp5 Knapsack table ltIgt 1 n 12 123 1234 12345 CI CI CI CI H IIIIH OPT 4 3 value 22 18 2 40 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodn IIIIH W n EC 0 O O O O O O O O O O 1 1 7 24 24 22 28 M 1 1 1 7 25 28 29 2 3 4 5 1 7 25 29 34 1 7 25 29 34 6 18 22 28 1 7 25 11 1 2 5 6 7 How do we make turn this into 9 Dynamic programming and divide and conquer lends itself directly to induction Base cases OPTiOO OPTOWO no items Inductive step explaining the correctness of recursive formula 0 If the following values are correctly computed OPT0wlOPT1wl OPTnwl OPT0W OPTilw 0 Then the recursive formula computes OPTiw correctly Case 1 Case 2 from previous slide 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne About proofs Proof is a rigorous argument about a mathematical statement s truth Should convince you Should not feel like a shot in the dark What makes a proof good enough is social Truly rigorous machinereadable proofs exist but are too painful for human use In real life you have to check your own work Ideal all problems should have grades 100 or 15 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 3 1quot Time and Space Complexity Given n objects and a quotknapsackquot Item i weighs wi gt O kilograms and has value vi gt O Knapsack has capacity of W kilograms Goal ll knapsack so as to maximize total value W 11 What is the input size value weight In words 1 1 1 In bits 2 6 2 3 18 5 4 22 6 5 28 7 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne 51 quotVI Time and space complexity Time and space n W Not polynomial in input size quotPseudopolynomial Decision version of Knapsack is NPcomplete KT chapter 8 Knapsack approximation algorithm There is a polytime algorithm that produces a solution with value Within 001 of optimum KT section 118 1082008 A Smith based on slides by E Demaine C Leiserson S Raskhodnikova K Wayne RNA Secondary STrucTure Problem RNA STring B blbzbn over alphabeT A C G U Secondary sTrucTure RNA Tends To loop back and form base pairs wiTh iTself This sTrucTure is essenTial for undersTanding behavior of molecule C A EX39 GUCGAUUGAGCGAAUGUAACAACGUGGCUACGGCGAGA A A A 39U o c l l C39G U A A G I I I I G I I I U I A U U A I G A C G C U l I I I I G I I I I C G C G A GC I I G A U G complemen rary base pairs AU CG RNA Secondary STrucTure Secondary sTrucTure A seT of pairs 5 bi bJ ThaT saTisfy WaTsonCrick S is a maTching and each pair in S is a WaTson Crick complemenT AU UA 66 or GC No sharp Turns The ends of each pair are separaTed by aT leasT 4 inTervening bases If bi bJ E S Then i ltj 4 Noncrossing If bi bJ and bk bl are Two pairs in S Then we cannoT have i lt k lt j lt l Free energy Usual hypoThesis is ThaT an RNA molecule will form The secondary sTrucTure wiTh The opTimum ToTal free energy approximaTe by number of base pairs Goal Given an RNA molecule B blbzbn find a secondary sTrucTure S ThaT maximizes The number of base pairs RNA Secondary S rr39uc rure Examples Examples 6 G G G G 5 5 C U C U CG CG C U I I I IgtltI AU AU A G I I I I I I UA UA UA basepair AUGUGGCCAU AUGGGGCAU AGUUGGCCAU lt s4 gt ok sharp rur39n crossing RNA Secondary S rruc rure Subproblems FirsT aTTempT OPTJ 2 maximum number of base pairs in a secondary sTrucTure of The subsTring blbzbJ maTch bar and bn DifficulTy ResulTs in Two subproblems Finding secondary sTrucTure in blbzb1 Finding secondary sTrucTure in b1bf2bn1 OPT r1 4 need more subproblems Dynamic Programming Over InTervals NoTaTion OPTi J maximum number of base pairs in a secondary sTrucTure of The subsTring bibi1bj Base case If i zj 4 OPTi j O by nosharp Turns condiTion Case 1 Base bJ is noT involved in a pair OPTi j OPTiJ1 Case 2 Base bJ pairs wiTh br for some i s T ltj 4 noncrossing consTrainT decouples resulTing subproblems OPTi J 1 maxr OPTi T1 OPTT1 J1 Take max over T such ThaT i s T lt J4 and bT and bJ are WaTsonCrick complemenTs BoTTom Up Dynamic Programming Over InTervals Q WhaT order To solve The subproblems A Do shorTesT inTervals firsT RNAb1bn Ignoring base cases for k 5 6 n 1 for i 1 2 j i k Compute Mi j 1 n k wt04gt return M 1 n using recurrence Time 0n3 Space 0n2 Exercise Find The secondary sTrucTure ThaT achieves The max value Dynamic Programming Summary Recipe Recursiver define value of opTimal soluTion CompuTe value of opTimal soluTion ConsTrucT opTimal soluTion from compuTed informaTion Dynamic programming Techniques Binary choice weighTed inTerval scheduling MulTiway choice segmenTed leasT squares KT secTion 63 Adding a new variable LCS knapsack Dynamic programming over inTervals RNA secondary sTrucTure parsing algori rhm for confexTfree grammar has similar sfrucfure Topdown memoizaTion vs boTTomup differenT people have differenT inTuiTions Algorithm Design and Analysis m LECTURE 1s Dyn mic Programming Weighted Interval Scheduling Sofya Raskhodnikova m l Algorithmic Paradigms Greedy Build up a solution incrementally myopically optimizing some local criterion Divide andconquer Break up a problem into subproblems solve each subproblem independently and combine solution to sub problems to form solution to original problem Dynamic programming Break up a problem into a series of overlapping subproblems and build up solutions to larger and larger subproblems Dynamic Programming History Bcllman 1950s Plonzzrzd inc sysicmaiic siudy of dynamic programmmg Etymology Dynamic programming planning over iimc Sccrciary of Defensz was nosiilc io maincmaiical rcscarcn Bcllman sougni an imprcssiyc namc io avold confrontation it39s impassible in usa dynamic in a pejur lwz sense sameining nor even aCungressman caula algaci in m amm a E smrrnnnmmwormpo Dynamic Programming Applications rcas Blolnformallcs Opcraiions rascarcni Compuicrscicncc lhzorygraphlcsAIc0mpll2rssysl2ms Somc famous dynamic programming algoriinms Unlx aim for comparing ino fllBSi f g a g 2 or lt 3 1 SmllhrWalzrmaVl for gcnciic sequencc allgnmzm Bellmaanord for snoricst pain rouiing in networks CockzyKasamlyVoungzr for parsing conicxi free grammars Weighted Interval Scheduling Wcignicd inicryal scncduling problcm obg iari J rinisncs ai g and nas ncigni or yaluc VJ Twogobs compaiiblc it incy don t oycrlap soal rind maximum ncigni subsci of muiually compatiblzgobs Unwaiglited Interval Scheduling kzview Recall erccay algoriinm works it all ncignis arci Consl dzrgobs in asccnding ordcr of rinisn iimc Addgob io subsci it ii is compaiiblc niin prcyiously choszngobs obscryaiion srccdy algoriinm can fail spcciacularly it arbiirary ncignis arc alloncd Mm iii Mignisi a Weighted Interval Scheduling Notation Labelgobs by finishing time n Q I J Def pg largest index i ltJ such lhalJob i is compatible WHHJ Ex pE 5 p7 3 p2 0 4 1 s 1 1 i 1 1 1 1 i s 1 y 1 1 1 1 i 1 1 c i 1 I n 4 s s i r a u Dynamic Programming Binary choice Notation 02m value of optimal solution to the problem consisting ofJob requests 12 J 052 1 OPT szlzclsJobJ ecollect profllv39 e can t use lncompallblzJobs pm 1 pg 2 J e l 7 must include optimal solution to problem consisting of remaining compallblzJobs 12 pg 052 2 OPT does not szlzclJobJ e must include optimal solution to problem consisting of remaining compallblzJobs 12 Jrl BETH 0 tr jcg imp 0PTfp j 0117114 omerwlse Weighted Interval Scheduling Brute Force Brute force algorithm Input a shrug fiiii vyrrvn Sun I by mach cuties sa but I s z s 5 computla pm pier w pull recum mtv e cmmnptlpljlli ContpubeOptljdl Weighted Interval Scheduling Brute Force observation Recurslvz algorithm falls spectacularly because of redundant suheproblems 2 exponential algorithms E u b of recursive calls for famlly of layered instances grows lihe Flbonaccl sequence Review Question Prove that the solution to the recurrence TtnInelIne2 eat is exponential in Yl Weighted Interval Scheduling lliiemoization Memolzallon Store results of each subrproblzm M a table loohup as needed Input n sums Irma v1v Sort jabs by flnxsh JimS do that f 4 I s s 2 n Comma Fmr pm Pl l f r 7 x 1 to a 3931 1 WW Mm 7 a ir wcanpdmwpctp t 1f mm n wpgyl mm 2 main t nvcompnm e39pctpljll wcmmwpctjatl return mm Weighted Intenval Scheduling Running Time claim Memolzzdvzrslon of algorithm lakes on log n time Sort by tinish time on lo n Computing p on log nviasorting bv start time neccnpaceeopctgi each invocation lakes 01 time and either 7 i returns an existing value m 7 ii fills in one new enirv um and makes two recursive calls Progress measure lt9 23 nonzmply entries ofmll e initiallvagt 0 throughout Q5 n 7 ii increases so bvl 2 at most 2n recursive calls Overall running time ofmrcompnteroptml is 0n Remark 0Vl mobs are preesorted by start and finish times Weighted Interval Scheduling Finding a Solution Q bvnamic programming algorithms computes optimal value Whal if we wam lhz solu lszlf A Do some poslrproczsslng Run M CWA lt 0 M Run nudesomtmnlni imatsuuumm 1 a j oi autpu nothing else Jf iv t MlPUH gt 111 1711quot 3 had Somme lia t le else nud solumm tam 2 of recursive calls g n 2 000 Weighted Interval Scheduling BottomUp Bollomrup dynamic programming Unwtnd recursion Input n 4 f1 I v r vrv Suit 1w by hum cuties ea um i s r s t x g Coxth pm pizl w pm Imuxva cauwtemp l may n a for j a 1 ma 391 MW F MlPlJtlN1H Algorithm Design and Analysis LECTURES 25 26 Network Flow 0 Maximum FOW 0 Minimum Cut 0 FordFulkerson Sofya Raskhodnikova 10242007 S Raskhodnikova based on slides by E Demaine C Leiserson K Wayne Soviet Rail Network 1955 Reference 0n the history of the transportation and maxmum fow probems Alexander Schrijver in Math Programming 91 3 2002 Maximum Flow and Minimum Cut Max flow and min cut Two very rich algorithmic problems Cornerstone problems in combinatorial optimization Beautiful mathematical duality Nontrivial applications reductions Data mining V Network reliability Openpit mining V Distributed computing Project Selection V Egalitarian stable matching Airline Scheduling V Security of statistical data Bipartite matching V Network intrusion detection BaSeball elimination V Multicamera Scene reconstruction Image segmentation V Many many more Network connectivity Minimum Cut Problem Flow network Abstraction for material flowing through the edges 6 V E directed graph no parallel edges Two distinguished nodes 3 source t sink Ce capacity of edge e Cuts Def An st cut is a partition A B of V with s e A and t e B Def The capacity of a cut A B is capA B Z Ce 2 out ofA s e lo lt9 4 6 15 10 Capacity 10 5 15 4 30 Q 30 2 9 10 4 15 source 5 5 gt 8 15 4 6 capacity 39 4 3O 7 7 Cuts Def An st cut is a partition A B of V with s e A and t e B Def The capacity of a cut A B is capA B Z Ce 2 out ofA 10 15 15 10 8 x9 10 CD 6 15 10 Capacity 9 15 8 30 62 Minimum Cut Problem Mm 5E1 c111 prab12m F1nd an 5E1 2111 of m1n1mum capac11y Flows D21 An 1111 1s a mnc11an 1 from E 10 rza1r1umb2rs 1na1 sa11sf1zs For 2acn 2 E E o 5 m1 212 capac11y For 2a211 y E v E15 1 EN 2m 1201132111a11a111 Def T112 711 ofa ow s Vf 2fe1 1 5k x gt A 15 1 1 51111 51 W 721 Flows Def An quot1111115 amnc11an 1 from E 111 rza1r1umb2rs 1na1 sa11s112s n E o 5 m1 2 1 1 covacw For 2a2n y E v E121 m m cov1sz1 va11on D21 1n21115101a11aw11s1 1111 2112 1 11 H In A 15 15 1 11 5 1 x 03 m 0 1 11 capacwy E15 1 15 11 m 9 an Wowzw 1 11 m A A 15 15 1 1n 3 5 C33 3 Q m 11 15 1 capamy 439 15 quot 11 11111 4 1 Vniuz x 51 Maximum Flow Problem Max ow 1110111211 Fmd SE1 ow 01 magtlt1mum ya112 V 6 111 I 11 A 15 15 1 11 r m 5 g 1 11 11 1 1 15 11 15 11 capaufy a 15 A A W Hues Flows and Cuts Haw va1u212mma 121 1 be any owar1d121ABb2 any SE1 211 111211 1112 1121 ow 52111 across 1112 C111 15 2qua11o 1112 11111011111 12ay1ng s Z el Z e vf 1511511 1111151 1 lt9 1 10 K 1 Vqu39 Flows and Cuts F10wva1u212mma 121 1 be any ow and 121 A B be any SE1 211 111211 1112 1121 ow 52111 across 1112 C111 15 2qua11o 1112 11111011111 12ay1ng s Z el ZfEe vf 1511511 111151 4 15 15 1 11 5 1 gt13 11 k 1 11 1 1 15 1 m 15 11 111511421511 3n 94 Flows and Cuts Flows and Cuts Fiow vaiuz iemma Let t be any ow and iet A B be any set out Fiaw vaiuz iemma Let t be any ow and iet A B be any set out Then Then the net ow sent across the cut is equai to the amount ieaytng s 2 f 2 Ne Vfv MA Z e E e V0 e am A Proof vf Z e M v 5 byhwcansltvmnnuH rms 2 L 2 ak 2 fe yeA waxy mptmmn my I it y n A A Z fie 2 ev emu a x a w A i N m it i 15 i m U H hhglarnarnom an 24 Flows and Cuts Flows and Cuts Weak duaiity Let t be any ow and iet A B be any set out Then the Weak duahty Let t be any aw Thenyt g capA B for any set out yaiue at the aw is at most the capactty at the out A B Cmmpmtynii 5 Hawtanegao Pf Vf 2 ak 2 e emu NA 2 V WI g 2 c J m A is is in ma PM 3 s x Q In 39 A is A 5 m 9 an Cop city an Certificate of Optimality Towards a Max Flow Algorithm Caraiiary Let t be any ow and iet A B be any set cut ereedy aigarithm It yt capA B then f is amax ow and A B is a min set out Start wtth e a for aii edge e E E Find an set path P where each edge has e A ce Vaiw atftaw ZS Augment aw aiang path P Cutcupactty 29 Finw vantage Repeat unttiyou get stuck at v a ti Iquot 4 t is is it m an in A 1 3n n 5 x i m i 4 it A 5 4 n t is H m m an M m it it How valung I so Towards a Max Flow Algorithm Greedy algorithm rt With 2 o for all 22192 2 E E Ema an 54 path P wh2r2 2a2h 22192 has 2 2 22 Aagm2ht ow along path P R2p2at until you g2t stuck Towards a Max Flow Algorithm Greedy algorithm Start With 2 o for all 22192 2 E E Find an 54 path P wh2r2 2a2h 22192 has 2 2 22 Aagm2ht ow along path P R2p2at unlllyou g2t it lacallyaptlmallty pglahal optimality it all Hi 21 m m in SE 3 30 W 1D in in Z ii at m an gmedy 20 opt z 30 v it Zn in an A2 in 2n ii a it How value a 20 Residual Graph Orlglrlal 22192 2 uv E E cwamw Elow 2 Caperle 22 C 17 A Flaw Residual 2dg2 Undo ow 22m M d dcmm 2avahd2rltva N Y stldualcapaclly E ii jg FordFulkerson Algorithm 22rf2 If 22 E 6 ate e if 2 E E maiudcapmlvy Residual graph 5 v E R2sidual 2dg2s With positiv2 residual capacity Ef 2 2 A 22 2 2R 22gt o FordFulkarsoh Algorithm 0 aw 4 lt i t 6 U 0 U 2apa2i y 10 2 0 B 6 0 10 Q4 E 0 quot gt3 10 9 10 Flaw value 0 FordFulkerson Algorithm 0 4 aw capacity 6 S ta xi l3 3 a 0 10 t 0 a la 10 9 10 F39lwt value 0 4 a residual 2apa2ity 6f 10 2 E a 10 240 32 9gt2L 13o FordFulkersan Algorithm 5 10 g ii 10 2 a 60 10 2 m g 2 102 10 9 10 Flaw mine 9 4 64 a 2 6 10 2 a 5 mm 0 2 E gtELC iii 9 FordFulkerson Algorithm 10 2 2 6 10 6 la 6 2 a lo 10 9 10 How value 10 4 sf 10 2 a 6 10 gig 7 gt49 10 gt3 2 FordFulkerson Algoriihm 3 Z 4 6 10 E X E 10 2 2 E 66 10 r 0 ii a 10 lo 9 10 How wing x 16 4 3 sf 6 10 2 a 6 4 6 E FordFulkerson Algoriihm 23 4 6 lo 37 3Q a 66 10 10 2 o a 9 g 9 10 lo 9 10 How mo x 15 2 2 sf 3 lo 2 E 6 2 FordFulkerson Algoriihm 3 4 5 10 7 9 10 2 0 B 6 6 10 9 lo 10 9 10 Flaw Mu 19 3 l sf 1 9 10 2 7 6 l FordFulkerson Algoriihm CM madly x 19 Flow will 19 Augmenting Path Algorithm Augmuut c E r bozclarremu Mm quotmoaownyon anng n foreaoh a a p 4 J A a n ma 4 am e 1 ammo so Le P 1m b ag X 12mm r PMaAHuKuNan a a t cw 1 romacn a a m rm 0 a 42 manna g rapb mea mum is an 54 pm 9 An at g t nxqnnmt c m math ax gt mum MaxF low MinCut Theorem Augm2nnng path theorem How f s amax ow w there are no augmzmmg paths Maxr ow mmrcut theorem Enasrrmnsmnrsnannon wars Forarrowson mo Th2 va uz of M2 max ow 5 2qua to M2 va uz of m2 mm s4 cm w W2 prove both swmuhanzous y by showmg aquot mam zqmvmzm w There 2 A B web that ym capA B n How f s amax ow and AB 5 mm s4 cm m There s no uugmzmmg path rzk39mvz to f x w 2 n Thxs was n2 coroHary to weak duahty zmma n 2 m W2 snow comraposmvz 2 a ow If there zxxsts an augmzmmg path then W2 can mprovz f by sendmg ow arong path Proof of MaxFlow MinCut Theorem m 0 L2 f b2 a ow wnn no augmzmmg paths L2 A b2 52 ofvzrnczs reachubm from s m rzswdum graph By dz nmon MA 3 E A By dz nmon of f v 2 A Vf E f Z e We um 22 nmgma n2 wank Running Time Assumpnon AH capacmzs ar2 Wzgzr s b2vw22n 1 and C Invamam Every ow va uz 2 and every rzswduw capacny c 2 r2mams an Wzgzr throughout M2 agomhm Tb2or2m Th2 a gomhm Vermmatzs m a mosv yfg nc Hzranons w Each augmzmanon mcrzasz va uz by at zastl Runmng mn2 of Fovdrmmson 0mnC 5pa22 0mon CoroHary If c 1FordrFuk2rson runs m 0mn mn2 Inmgrahry rh2or2m If aH capacmzs ar2 mr2g2rs vh2n rh2r2 2mm a max ow f for Web 2y2ry ow va uz 2 s an mrzgzr w Smcz a gorwhm termmatzs theorem foHows from mvamam Algorithm Design and Analysis LECTURE 35 Computational l 5 Intractability Polynomial Time Reductions Adam Smith A Smith based on slides by S Raskhodnikova K Wayne 11192008 This chapTer compuTaTional in rr ac rabili ry and NP Goal under39s rand wha r canno r be compu red can you name some hard problems Compu rabili ry canno r even in principlequot Complexi ry cannoT given reasonable r39esour39cesquot we focus on complexiTy here why Cen rr39al ideas polyTime as feasible mos r na rur39al problems are ei rher39 easy or39 have no known sh 2 polyTime algor39i rhms nunreasomble NP and NPcomple reness affec fizeness P pr39oblems ThaT are easy To answer39 ma rhgma rics eg minimum cu r i SCiencequot NP 2 problems whose answers are easy To verify given hin r 39 eg gr39aph 3color39ing NP comple reness many naTural problems are easy if and only if PNP So far39 under39sTand alg design Examples Greedy On log n inTer39val scheduling Divideandconquer39 On log n FFT Dynamic programming 0n2 ediT disTance DualiTy eg MaxFlowNlinCuT On3 bipar39TiTe maTching ReducTions Local search Randamlza on New goal under39sTand whaT is hard To compuTe NPcompleTeness Onkalgor39iThm unlikely PSPACEcompleTeness Onk cer TificaTion algor39iThm unlikely UndecidabiliTy No algor39iThm possible Problems in P Problems in NPcomplete PSPACE Undecidable NP not known complete to be in P or NPcomplete max ow factoring longest path TQBF totally halting problem t39f d knapsack w1th graph traveling gum 1 le oolean fractional isomorphism salesman formula elements in h 1 knapsack grap CO O ng Given a game 35m with polysize board independent set con gurations knapsack W decide if White fract weights has Wmmng strategy 11 19 2008 A Smith based on Slides by S Raskhodnikova K Wayne UndersTanding quothardnessquot CompuTabiliTy UndersTand whaT cancannoT be compuTed even in principle HalTing problem given program code will This program geT sTuck in an infiniTe loop Theorem Turing halTing problem is uncompuTable so mosT Things we wanT compilers To do are undecidable Corollary Some numbers are Too big To compuTe busy beaver problem BBnmax of sTeps ThaT an ncharacTer C program ThaT sTops evenTually can Take before iT sTops If you could compuTe an upper bound on BBn you could solve The halTing problem CompeTiTion Think of The biggesT number you can ComplexiTy UndersTand whaT problems cannoT be solved in a reasonable amounT of Time Far less is known Famous problem P vs NP unreasonable effectiveness of ma rhema rics in sciencequot Cen rr al ideas we39ll cover39 PolyTime as feasible mos r na rural problems ei rher39 are easy say n3 or have no known polyTime algori rhms Reduc rions X is no harder Than Y P 2 problems Tha r are easy To answer eg minimum cu r NP 2 problems whose answers are easy To verify given him eg graph 3coloring NPcompleTeness many na rural problems are easy if and only if PNP WhaT do we mean by quotfeasiblequot Q Which problems will we be able To solve in pracTice A working defini l39ion von Neumann 1953 Godel 1956 Cobham 1964 Edmonds 1965 Robin 1966 Those wiTh polynomialTime algoriThms Yes Probably no Shor39fesf pa39rh Longesf paTh MaTching 3Dma rching Min cuT Max CUT 2SAT 3SAT Planar 4color39 Plan ar 3color39 Bipar TiTe ver39Tex cover39 Ver39Tex cover39 Pr39imalify Tesfing FacTor ing Classify Problems DesideraTa Classify problems as Those ThaT can be solved in polynomialTime and Those ThaT cannoT Roughly C program on machine wiTh Provably require exponenTial ime 39 f39n39Te memory Given a Turing machine does iT halT in aT mosT k sTeps Given a board posiTion in an nbyn generalizaTion of chess can black guaranTee a win FrusTraTing news Huge number of fundamenTal problems have defied classificaTion for decades This chapTer Show ThaT These fundamenTal problems are quotcompuTaTionally equivalenTquot and appear To be differenT manifesTaTions of one really hard problem Tool PolynomialTime Reduc rion DesideraTa39 Suppose we could solve X in polynomialTime WhaT else 9 could we solve In polynomial Time donf confuse wifh reduces from ReducTion Problem X polynomial reduces To problem Y if arbiTrary insTances of problem X can be solved using Polynomial number of sTandard compuTaTional sTeps plus Polynomial number of calls To oracle ThaT solves problem Y compuTaTional model SupplemenTed by special piece of hardware ThaT solves insTances of Y in a single sTep NoTaTion X s PICook Y or X s P Y LaTer in The ecTure X s P Karp Y Remarks We pay for Time To wriTe down insTances senT To black box gt insTances of Y musT be of polynomial size PolynomialTime ReducTion Purpose Classify problems according To r39elaTive difficulTy Design algor39iThms If X s P Y and Y can be solved in polynomialTime Then X can also be solved in polynomial Time EsTablish inTr39acTabiliTy If X s P Y and X cannoT be solved in polynomialTime Then Y cannoT be solved in polynomial Time EsTablish equivalence If X s P Y and Y s P X we use noTaTion X a PY up To cosT of r39educTion Simpliinng Assumption Decision Problems Search problem Find some structure Example Find a minimum cut Decision problem X is a set of strings Instance string 3 If xe X x is a YES instance if xi X is a NO instance Algorithm A solves problem X As yes iff s E X Example Does there exist a cut of size s k Selfreducibility Search problem s PICook decision version Applies to all NPcomplete problems in this chapter Justifies our focus on decision problems Polynomial TransformaTion Def Problem X polynomial reduces Cook To problem Y if arbiTrary insTances of problem X can be solved using Polynomial number of sTandard compuTaTional sTeps plus Polynomial number of calls To oracle ThaT solves problem Y Def Problem X polynomial Transforms Karp To problem Y if given any inpuT x To X we can consTrucT an inpuT y such ThaT x is a yes insTance of X iff y is a yes insTance of Y we require IyI To be of size polynomial in IXI NoTe Polynomial TransformaTion is polynomial reducTion wiTh jusT one call To oracle for Y exachy aT The end of The algoriThm for X Open quesTion Are These Two concest The sarTne CauTion KT abuSes noTaTion sp and blurs disTincTion Algorithm Design and Analysis Network Flow Application Edge Disjoint Paths Extensions m LECTURE 31 g Sofya Raskhodnikova Edge Disjaiht Paths Prab12m etu2h a dtgr aph e v E and two had2s s and t tmd th2 max number at 2dg2dtsJomf 5 paths b2t Two paths are 2dg2dtsJ0mf 1f they hau2 ha 2dg2 m common Ex commumcatton networks Edge Disjaiht Paths DtsJomf path prab12m etu2h a dtgraph e v E and two had2s s and t t h2 max number at 2dg2dtsJotm 5 paths b2t Two paths are 2dgbdtsJoW 1f they hau2 ha 2dg2 m common Ex commumcatton networks Edge Disjaiht Paths Max ow tarmutattam asstgh umt capactty to every 2dg2 Theorem Max number 2dg2dtsJOW 5 paths 2qua1s max ow ua1u2 Pt lt Suppas2 th2r2 are k 2dg2dtsJotm paths P Pk 52t f211f 2 parttctpat2s m sam2 path P 21s2 s2t f20 Smcz paths are 2dgbdtsJoW t ts a ow at ua1u2 x Edge Disjaiht Paths Max ow tarmutattam asstgh umt capactty to every 2dg2 1 KW sw Theorem Max number 2dg2dtsJotm 5 paths 2qua1s max ow ua1u2 Pf 2 max ow ua1u2 ts x 1ht2grahtyth2ar2m 2 th2r2 2xtsts 01 ttawt atuatu2 x Constdzr 2dg2tsuw1th fs u 1 e by cahs2ruattah th2r2 2xtsts ah 2dg2 u v thh ttu v 1 commuz uhttt reach t atways chaasmg a h2w 2d 2 Produces xthath2c2ssamty stmp z2dgbdtsJomfpmhs can 211mmat2 systes ta get stmpte paths 1f destred Network Connectivity Network cahh2cttutty etu2h adtgraph e v E and two had2s s and t mm mm number at 2dg2s whas2 r2maua1dtscahh2cts t from s b2t A s2t at 2dg2s F E dtscahmts t from s 1t 2ach 5 paths us2s at 2ast on2 2dg2 m F Theorem Each srt paths uses at izast one ngzrdisJomt paths is at mos Edge Disjoint Paths and Network Connectivity Manger 1927 Th2 max number of zdgzrdisJomt sit path equai to the mm number of edges whose removai disconnects t Pom Pf Suppose the removai of F g E disconnects t from s and m x c2 the number of p Disjoint Paths and NetworkConnectivity Theorem Manger 1927 The max number of zdgzrdisJomt sit paths is equai to tha mm number of Edges whose removai disconnects 7 from s Pt 2 Suppose max humbzr of ngzrdisJomt paths is k Then max ow vaiuz is k Maxr ow mtmcut gt out A B of Capacity x Let F be s t dgzs going from to B iFi x and disconnects t tr m s 77 Extensions to Max Flow Circulation with Damunds Necessary condition sum of suppiies sum V of demands 7 dy x v 0 v dvlt 0 Proof Sum conservation constraints for every demand node v u re k suppiy a i 4 4 u n 4 39 t i W V demand ow Circulation with Demands Circuiation With demands dgraph6vE Edge capactttas Cz E Node suppiy and demands dv v E v demand it am gt o suppiy it am lt o transshipment it am 0 that satisfies 2 s Cz 22 r Z e 1th mm am it t misafuhcttoh For 2ach 2 E O s For each v E tcapacttyt conservation t Circuiatton probizm given v E c d does thm exist acmcutattw Circulation with Damunds Max ow formuiatiott 8 re k suppiy 7 Cgt u m Circulation with Demands Max ow formulallorl source s and slnxl For each wllh dv lt 0 add edge s v wllh capaclly edu For each v wllh dv gt0 add edge v l wllh capaclly dv Clalm s has clr culallon lrrel has max flow of value D saturates all edges cwl le ng s and enlermg l 7 7 o supply 7 m a 4 u m E demand Circulation with Demands Inlegrallly lneorem In all capacllles and demands are lnlegers and eXlSlS aclrculallon then there eXlSlS one that ls lnlegerrvalued Proof Follows from max flow formulallorl and lnlegrallly lneorem for ax ow cnaraelerlzallon 6lve lV E c d lnere does n 39exlsls aclrculallon lrr lnere exlsls a node parllllon A B such Mar 26ng gt capA B Proof dza Look a W cu m 9 demand by nudes m B exceeds supply an nudes m B plus max capaclly an edges gulng frnm A la B Circulation with Demands and Lower Bounds Feaslble clr culallon blrecred graph 6 v E Edge capacllles Ce and lower bounds e e e E Node supply and demands dv v e v berlnlllon Al lsa mcllonlhalsallsfles ForeacheEE 2e s fe s Ce Capaclly J J icons mall Foreachvsv 2M 2K2 dtv onl e on man Clr culallon problem wllh lower bounds leer l v E l c d does mere eXlSYS a a clrculallon Circulation with Demands and Lower Bounds Idea Model lower bounds wllh demands Send e Lmlls of ow along edge e Updale demands of both endpolnls lowoouna upwoouna enraeny l l i 291 Q 7 M 5 W dvo2 5 dwez Theorem There exlsls a elrculallon m6 lrr mere exlsls aclrculallon ln 6 If all demands Capacllles and lower bounds ln s are lnlegers then there ls aclrculallon m that ls lnlegerrvalued Proof sxelen fe is a clr culallon m s lrr f e ree e is a clrculallon M 6 Algorithm Design and Analysis 3 1 g LECTURES 2526 3 m 2connectivity E3 H Midterm discussion Adam Smith A Smith based on slides by S Raskhodnikova and K Wayne 10222008