ancakeswithaProblem：有问题的煎饼.ppt

PancakesWithAProblem CourseStaff Profs AnupamGuptaJohnLaffertyTAs KanatTangwongsanYinmengZhanghttp www cs cmu edu 15251Pleasecheckthewebpagesregularly Pleasefeelfreetoaskquestions CourseDocumentYoumustreadthiscarefully Gradingformulaforthecourse 40 homework5 in classquizzes25 in recitationtests30 finalSevenpointsadaylatepenalty Collaboration CheatingPolicyYoumayNOTsharewrittenwork Wereusehomeworkproblems PancakesWithAProblem Thechefatourplaceissloppy andwhenhepreparesastackofpancakestheycomeoutalldifferentsizes Therefore whenIdeliverthemtoacustomer onthewaytothetableIrearrangethem sothatthesmallestwindsupontop andsoon downtothelargestatthebottom Idothisbygrabbingseveralfromthetopandflippingthemover repeatingthis varyingthenumberIflip asmanytimesasnecessary DevelopingANotation Turningpancakesintonumbers DevelopingANotation Turningpancakesintonumbers DevelopingANotation Turningpancakesintonumbers 2 3 4 5 1 DevelopingANotation Turningpancakesintonumbers 52341 Howdowesortthisstack Howmanyflipsdoweneed 52341 4FlipsAreSufficient 12345 52341 43215 23415 14325 AlgebraicRepresentation 52341 X Thesmallestnumberofflipsrequiredtosort X UpperBound LowerBound AlgebraicRepresentation 52341 X Thesmallestnumberofflipsrequiredtosort X 4 UpperBound LowerBound 4Flipsarenecessaryinthiscase 52341 41325 14325 Flip1hastoput5onbottomFlip2mustbring4totop UpperBound LowerBound 4 X 4 5thPancakeNumber Thenumberofflipsrequiredtosorttheworstcasestackof5pancakes P5 UpperBound LowerBound P5 5thPancakeNumber Thenumberofflipsrequiredtosorttheworstcasestackof5pancakes 4 P5 UpperBound LowerBound P5 The5thPancakeNumber TheMAXoftheX s 120 1 199 3 2 X1 X2 X3 X119 X120 52341 4 The5thPancakeNumber TheMAXoftheX s 120 199 3 X1 X2 X3 X119 X120 52341 4 12345 54321 120 199 3 X1 X2 X3 X119 X120 52341 4 12345 54321 P5 MAXovers2stacksof5ofMIN offlipstosorts Pn MAXovers2stacksofnpancakesofMIN offlipstosorts Pn Thenumberofflipsrequiredtosorttheworst casestackofnpancakes Pn MAXovers2stacksofnpancakesofMIN offlipstosorts Pn Thenumberofflipsrequiredtosortaworst casestackofnpancakes BeCool LearnMath speak Pn Thenumberofflipsrequiredtosortaworst casestackofnpancakes WhatisPnforsmalln Canyoudon 0 1 2 3 InitialValuesOfPn P3 3 132requires3Flips henceP3 3 ANYstackof3canbedonebygettingthebigonetothebottom 2flips andthenusing 1extrafliptohandlethetoptwo Hence P3 3 nthPancakeNumber Thenumberofflipsrequiredtosortaworstcasestackofnpancakes Pn UpperBound LowerBound Pn Bracketing WhatarethebestlowerandupperboundsthatIcanprove Pn TakeafewminutestotryandproveupperandlowerboundsonPn forn 3 Bringbiggesttotop Placeitonbottom Bringnextlargesttotop Placesecondfrombottom Andsoon Bring to topMethod UpperBoundOnPn BringToTopMethodFornPancakes Ifn 1 noworkrequired wearedone Otherwise flippancakentotopandthenflipittopositionn Nowuse BringToTopMethodForn 1Pancakes TotalCost atmost2 n 1 2n 2flips BetterUpperBoundOnPn BringToTopMethodFornPancakes Ifn 2 atmostoneflipandwearedone Otherwise flippancakentotopandthenflipittopositionn Nowuse BringToTopMethodForn 1Pancakes TotalCost atmost2 n 2 1 2n 3flips Bringtotopnotalwaysoptimalforaparticularstack Bring to toptakes5flips butwecandoin4flips 32145 52341 23145 41325 14325 Pn 2n 3 WhatotherboundscanyouproveonPn 916 SupposeastackScontainsapairofadjacentpancakesthatwillnotbeadjacentinthesortedstack AnysequenceofflipsthatsortsstackSmustinvolveoneflipthatinsertsthespatulabetweenthatpairandbreaksthemapart BreakingApartArgument 916 SupposeastackScontainsapairofadjacentpancakesthatwillnotbeadjacentinthesortedstack AnysequenceofflipsthatsortsstackSmustinvolveoneflipthatinsertsthespatulabetweenthatpairandbreaksthemapart Furthermore thissameprincipleistrueofthe pair formedbythebottompancakeofSandtheplate BreakingApartArgument n Pn 2468 n1357 n 1 S Supposeniseven ScontainsnpairsthatwillneedtobebrokenapartduringanysequencethatsortsstackS n Pn Supposeniseven ScontainsnpairsthatwillneedtobebrokenapartduringanysequencethatsortsstackS 21 S Detail Thisconstructiononlyworkswhenn 2 n Pn Supposenisodd ScontainsnpairsthatwillneedtobebrokenapartduringanysequencethatsortsstackS 1357 n2468 n 1 S n Pn 132 S Detail Thisconstructiononlyworkswhenn 3 Supposenisodd ScontainsnpairsthatwillneedtobebrokenapartduringanysequencethatsortsstackS n Pn 2n 3forn 3 BringToTopiswithinafactoroftwoofoptimal StartingfromANYstackwecangettothesortedstackusingnomorethanPnflips n Pn 2n 3forn 3 FromANYstacktosortedstackin Pn Reversethesequencesweusetosort FromsortedstacktoANYstackin Pn Hence FromANYstacktoANYstackin 2Pn FromANYstacktosortedstackin Pn FromsortedstacktoANYstackin Pn FromANYstacktoANYstackin 2Pn Canyoufindafasterwaythan2PnflipstogofromANYtoANY FromANYStackStoANYstackTin Pn RenamethepancakesinStobe1 2 3 n RewriteTusingthenewnamingschemethatyouusedforS Twillbesomelist p 1 p 2 p n Thesequenceofflipsthatbringsthesortedstacktop 1 p 2 p n willbringStoT 1 2 3 4 5 3 5 1 2 4 TheKnownPancakeNumbers 12345678910111213 01345 n Pn 7891011131415 P14IsUnknown 14 Orderingsof14pancakes 14 87 178 291 200 IsThisReallyComputerScience PosedinAmer Math Monthly82 1 1975 HarryDweighter a k a JacobGoodman 17 16 n Pn 5n 5 3 WilliamGates ChristosPapadimitriouBoundsForSortingByPrefixReversal DiscreteMathematics vol27 pp47 57 1979 15 14 n Pn 5n 5 3 H Heydari H I SudboroughOntheDiameterofthePancakeNetwork JournalofAlgorithms vol25 pp67 94 1997 Permutation AnyparticularorderingofallnelementsofannelementsetS iscalledapermutationonthesetS Example S 1 2 3 4 5 Onepossiblepermutation 532415 4 3 2 1 120possiblepermutationsonS Permutation AnyparticularorderingofallnelementsofannelementsetS iscalledapermutationonthesetS Eachdifferentstackofnpancakesisoneofthepermutationson 1 n RepresentingAPermutation WehavemanywaystospecifyapermutationonS Herearetwomethods Welistasequenceofalltheelementsof 1 n eachonewrittenexactlyonce Ex 645213Wegiveafunction onSsuchthat 1 2 3 n isasequencethatlists 1 n eachoneexactlyonce Ex 1 6 2 4 3 5 4 2 4 1 6 3 APermutationisaNOUN AnorderingSofastackofpancakesisapermutation APermutationisaNOUN ApermutationcanalsobeaVERB AnorderingSofastackofpancakesisapermutation WecanpermuteStoobtainanewstackS Permutealsomeanstorearrangesoastoobtainapermutationoftheoriginal PermuteAPermutation IstartwithapermutationSofpancakes Icontinuetouseaflipoperationtopermutemycurrentpermutation soastoobtainthesortedpermutation Therearen 1 2 3 4 npermutationsonnelements Easyproofinthefirstcountinglecture PancakeNetwork DefinitionForn Nodes Foreachnode assignitthenameofoneofthen stacksofnpancakes Putawirebetweentwonodesiftheyareoneflipapart NetworkForn 3 123 321 213 312 231 132 NetworkForn 4 PancakeNetwork MessageRoutingDelay Whatisthemaximumdistancebetweentwonodesinthenetwork Pn PancakeNetwork Reliability Ifupton 2nodesgethitbylightningthenetworkremainsconnected eventhougheachnodeisconnectedtoonlyn 1othernodes ThePancakeNetworkisoptimallyreliableforitsnumberofedgesandnodes MutationDistance HighLevelPoint ComputerScienceisnotmerelyaboutcomputersandprogramming itisaboutmathematicallymodelingourworld andaboutfindingbetterandbetterwaystosolveproblems Thislectureisamicrocosmofthisexercise One Simple Problem Ahostofproblemsandapplicationsatthefrontiersofscience StudyBee Pleasereadthecoursedocumentcarefully Youmusthandinasignedcheatingpolicypage StudyBee Definitionsof nthpancakenumberlowerboundupperboundpermutationProofof ANYtoANYin PnImportantTechnique Bracketing References BillGates ChristosPapadimitriou BoundsForSortingByPrefixReversal DiscreteMathematics vol27 pp47 57 1979 H Heydari H I Sudborough OntheDiameterofhePancakeNetwork JournalofAlgorithms vol25 pp67 94 1997