15 251 Great Theoretical Ideas in Computer Science 15 251 Great Theoretical Ideas in Computer Science www cs cmu edu 15251 Course Staf Instructors Victor Adamchik Danny Sleator TAs Drew Besse Adam Blank Dmtriy Chernyak Sameer Chopra Dan Kilgallin Alan Pierce Grading Lowest nonprogramming HW grade is dropped Final 20 In Class Quizzes 4 Homework Lowest quiz 50 dropped All tests counted 3 Tests 30 Weekly Homework Homeworks handed out Tuesdays except for a couple and are due the following Tuesday at midnight Ten points per day late penalty No homework will be accepted more than two days late Homework MUST be typeset and a single PDF file Collaboration Cheating You may NOT share written work You may NOT use Google or other search engines You may NOT use solutions to previous years homework You MUST sign the class honor code Textbook There is NO textbook for this class We have class notes in wiki format You too can edit the wiki Feel free to ask questions And take advantage of our generous office hours 15 251 Cooking for Computer Scientists Pancakes With A Problem Lecture 1 January 12 2010 The chefs at our place are sloppy when they prepare pancakes they come out all diferent sizes When the waiter delivers them to a customer he rearranges them so that smallest is on top and so on down to the largest at the bottom He does this by grabbing several from the top and flipping them over repeating this varying the number he flips as many times as necessary How do we sort this stack How many flips do we need How do we sort this stack How many flips do we need Developing A Notation Turning pancakes into numbers 5 2 3 4 1 5 2 3 4 1 How do we sort this stack How many flips do we need 5 2 3 4 1 5 2 3 4 1 4 Flips Are Sufficient 5 2 3 4 1 1 4 3 2 5 2 3 4 1 5 4 3 2 1 5 1 2 3 4 5 Best Way to Sort X Smallest number of flips required to sort Lower Bound 5 2 3 4 1 X 4 Upper Bound Can we do better 5 2 3 4 1 Four Flips Are Necessary 5 2 3 4 1 1 4 3 2 5 4 1 3 2 5 If we could do it in three flips Flip 1 has to put 5 on bottom else we would take 3 flips just to get 5 to bottom Flip 2 must bring 4 to top if it didn t we would take more than three flips 4 X 4 Lower Bound Upper Bound X 4 where X Smallest number flips required to sort 5 2 of3 4 1 5th Pancake Number Number of flips required to sort P5P 5 MAX over s stacks of 5 the worst case stack of 5 of MIN of flips to sort s pancakes 1 2 3 1 4 5 5 4 32 2 1 3 X1 X2 X3 5 2 3 4 1 4 1 1 9 X119 1 2 0 X120 5th Pancake Number Lower Bound 4 P5 There exists a 5 pancake stack which will make me take this much time Upper Bound For all 5 pancake stacks s we can sort s in this much time Pn MAX over s stacks of n pancakes of MIN of flips to sort s Pn The number of flips required to sort the worst case stack of n pancakes What is Pn for small n Can you do n 0 1 2 3 Initial Values of Pn n 0 1 2 3 Pn 0 0 1 3 P3 3 1 3 2 requires 3 Flips hence P3 3 ANY stack of 3 can be done by getting the big one to the bottom 2 flips and then using 1 flips to handle the top two nth Pancake Number Pn Lower Bound Number of flips required to sort the worst case stack of n pancakes Pn Upper Bound Bracketing What are the best lower and upper bounds that I can prove f x Pn Try to find upper and lower bounds on Pn for n 3 Bring to top Method Bring biggest to top Place it on bottom Bring next largest to top Place second from bottom And so on Upper Bound On Pn Bring to top Method For n Pancakes If n 1 no work required we are done Otherwise flip pancake n to top and then flip it to position n Now use Bring To Top Method For n 1 Pancakes Total Cost at most 2 n 1 2n 2 flips Better Upper Bound On Pn Bring to top Method For n Pancakes If n 2 at most one flip and we are done Otherwise flip pancake n to top and then flip it to position n Now use Bring To Top Method For n 1 Pancakes Total Cost at most 2 n 2 1 2n 3 flips Pn 2n 3 For a particular stack bring to top not always optimal 5 2 3 4 1 1 4 3 2 5 4 1 3 2 5 2 3 1 4 5 Bring to top takes 5 flips but we can do in 4 flips 3 2 1 4 5 Pn 2n 3 What other bounds can you prove on Pn Breaking Apart Argument Suppose a stack S has a pair of adjacent pancakes that will not be adjacent in the sorted stack Any sequence of flips that sorts stack S must have one flip that inserts the spatula between that pair and breaks them apart Furthermore this is true of the pair formed by the bottom pancake of S and the plate 9 16 S 2 4 6 8 n 1 3 5 n 1 n Pn Suppose n is even S contains n pairs that will need to be broken apart during any sequence that sorts it Detail This construction only works when n 2 2 1 S 1 3 5 7 n 2 4 6 n 1 n Pn Suppose n is odd S contains n pairs that will need to be broken apart during any sequence that sorts it Detail This construction only works when n 3 1 3 n Pn 2n 3 for n 3 Bring to top is within a factor of 2 of optimal From ANY stack to sorted stack in Pn From sorted stack to ANY stack in Pn Reverse the sequences we use to sort Hence from ANY stack to ANY stack in 2Pn Can you find a faster way than 2Pn flips to go from ANY to ANY ANY Stack S to ANY stack T in Pn S 4 3 5 1 2 T 5 2 4 3 1 1 2 3 4 5 3 5 1 2 4 new T Rename the pancakes in S to be 1 2 3 n Rewrite T using the new naming scheme that you used for S The sequence of flips that brings the sorted stack to the new T will bring S to T …
View Full Document
Unlocking...