Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 3515-251Great Theoretical Ideas in Computer ScienceaboutAWESOMESomeGeneratingFunctionsMORE Generating FunctionsLecture 7 (February 2, 2010)Adam BlankAnnouncementsYou are now breathing manuallyHomework 3 is due tonight•Please submit a collaborators graph again.•It doesn’t matter what you name it.•You do not also have to list your collaborators in the pdfHomework 4 is out•This assignment is non-trivial•Start early!Exam 1 will be in recitation next week•Don’t be late!•We will (tentatively) have a review session on Saturday•We will email you with updatesWhat good are Generating Functions anyway?What good are Generating Functions anyway?They're fun!Solving recurrences preciselyThey are often easier than the alternative!Some TerminologyClosed form of a Generating FunctionClosed form for a RecurrenceLet’s do some problems!Domino DominationWe have a board, and we would like to fill it with dominos. We have two colors of dominos: green and blue. The green ones must be used in pairs (so that they don’t get blue!), and they must be vertical. How many ways can we tile our board?Domino DominationWe have a board, and we would like to fill it with dominos. We have two colors of dominos: green and blue. The green ones must be used in pairs (so that they don’t get blue!), and they must be vertical. How many ways can we tile our board?This is a combinatorial question!How should we proceed?!?!Write a recurrence!Domino DominationSo now we have a recurrence…but now what?Domino DominationNow we derive a closed form using generating functions!LetWe know the base cases: Note that these base cases are actually correct.is the number of ways to tile a board.Domino DominationNow we derive a closed form using generating functions!LetDomino DominationNow we derive a closed form using generating functions!LetDomino DominationNow we have a closed form for the generating function!…what now?LetDomino DominationNow we have a closed form for the generating function!…what now?LetDomino DominationNow we have a closed form for the generating function!…what now?LetRogue RecurrenceSolve this recurrence…or else!Letfor n>2, ,Rogue RecurrenceSolve this recurrence…or else!Letfor n>2, ,Rogue RecurrenceSolve this recurrence…or else!Letfor n>2, ,Rogue RecurrenceSolve this recurrence…or else!Letfor n>2, ,What next? Partial fractions?Rogue RecurrenceNo. Let’s be sneaky instead!Rogue RecurrenceNow back to the recurrence…Letfor n>2, ,Double Sums OMGWTFBBQ!Let’s revisit the last lecture…We would like to swap the summations. All we have done here is re-group the addition.Double Sums OMGWTFBBQ!We know that…Double Sums OMGWTFBBQ!We know that…So…Dainty Diners2n nobles want to sit down to dinner at a table and shake hands. They are picky and will not shake hands in any way, in which one or more noble reaches over another. How many ways can the nobles shake hands?Dainty DinersLook at an arbitrary person, and think about who he could shake hands with.Dainty DinersNoble 0 can shake hands with 2, 4, or 6.He can shake hands with even numbered people! When he shakes hands with someone,it splits the remaining people into two groups.602345Dainty DinersFirst, we choose which person the 0th person shakes hands with, then we choose the two sub-groups created by this choice# of ways 2n nobles can shake hands# of ways 2k nobles can shake hands# of ways 2(n-k-1) nobles can shake handsChoose which person the 0th person shakes hands withDainty Dinersn=1:n>1:LetDainty DinersWhat now? Our usual trick of putting the terms in terms of P(x) doesn’t seem to be possible!Dainty DinersIdea! Isolate the double summation and list out some terms.Is there a pattern??Dainty DinersLet C(x) be an arbitrary generating function!Suppose we take k terms from the left. We need n-k from the second to make n total powers of k.Dainty DinersAfter some “magic” (see Newton’s Binomial Theorem):Here’s What You Need to Know…Generating Functions• How to solve recurrences• Summation techniques• Simple partial fractions• Simple differentiation(mostly remember how to use generating functions to solve
View Full Document
Unlocking...