15 251 Great Theoretical Ideas in Computer Science 15 251 Great Theoretical Ideas in Computer Science www cs cmu edu 15251 Grading Course Staff Instructors Victor Adamchik Danny Sleator TAs Drew Besse Adam Blank Dmtriy Chernyak Sameer Chopra Dan Kilgallin Alan Pierce Final 20 In Class Quizzes 4 Lowest nonprogramming HW grade is dropped 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 1 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 2 Pancakes With A Problem Lecture 1 January 12 2010 The chefs at our place are sloppy when they prepare pancakes they come out all different 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 How do we sort this stack How many flips do we need 5 2 3 5 2 3 4 1 5 2 3 4 1 4 1 3 5 2 3 4 1 4 Flips Are Sufficient 5 2 3 4 1 Best Way to Sort 2 3 4 1 5 4 3 2 1 5 1 2 3 4 5 Can we do better 5 2 3 4 1 X Smallest number of flips required to sort Lower Bound 1 4 3 2 5 5 2 3 4 1 X 4 Upper Bound Four Flips Are Necessary 5 2 3 4 1 1 4 3 2 5 4 1 3 2 5 4 X 4 Lower Bound Upper Bound X 4 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 where X Smallest number of flips required to sort 5 2 3 4 1 4 5th Pancake Number 5th Pancake Number flips required to sort the P5P 5 Number MAX of over s stacks of 5 worst case stack of 5 pancakes of MIN of flips to sort s 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 Lower Bound 4 P5 There exists a 5 pancake stack which will make me take this much time X120 Upper Bound For all 5 pancake stacks s we can sort s in this much time What is Pn for small n Pn MAX over s stacks of n pancakes of MIN of flips to sort s Can you do The number of flips required to sort the worst case stack of n pancakes Pn n 0 1 2 3 P3 3 Initial Values of Pn n 0 1 2 3 Pn 0 0 1 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 5 nth Pancake Number Pn Number of flips required to sort the worst case stack of n pancakes Lower Bound Pn Upper Bound Pn Bracketing What are the best lower and upper bounds that I can prove f x Bring to top Method Try to find upper and lower bounds on Pn for n 3 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 Better 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 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 Now use Bring To Top Method For n 1 Pancakes Total Cost at most 2 n 1 2n 2 flips Bring To Top Method For n 1 Pancakes Total Cost at most 2 n 2 1 2n 3 flips 6 For a particular stack bring to top not always optimal 5 2 3 4 1 Pn 2n 3 1 4 3 2 5 4 1 3 2 5 2 3 1 4 5 3 2 1 4 5 Bring to top takes 5 flips but we can do in 4 flips Breaking Apart Argument Pn 2n 3 What other bounds can you prove on Pn 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 9 16 Furthermore this is true of the pair formed by the bottom pancake of S and the plate S 2 4 6 8 n 1 3 5 n 1 S 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 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 2 7 n Pn 2n 3 for n 3 From ANY stack to sorted stack in Pn From sorted stack to ANY stack in Pn Reverse the sequences we use to sort Bring to top is within a factor of 2 of optimal Hence from ANY stack to ANY stack in 2Pn ANY Stack S to ANY stack T in Pn S 4 3 5 1 2 Can you find a faster way than 2Pn flips to go from ANY to ANY The Known Pancake Numbers n Pn 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 1 3 4 5 7 8 9 10 11 13 14 15 16 17 18 19 T 5 2 4 3 1 3 5 1 2 …
View Full Document
Unlocking...