Great Theoretical Ideas In Computer Science Steven Rudich Lecture 1 CS 15 251 Jan 13 2004 Spring 2004 Carnegie Mellon University Pancakes With A Problem Magic Trick At 3 00pm Sharp Be punctual Sit close up some of the tricks are hard to see from the back Course Staf Profs Steven Rudich Anupam Gupta TAs Yinmeng Zhang Bella Voldman Brendan Juba Andrew Gilpin Susmit Sarkar Adam Wierman Please feel free to ask questions Course Document You must read this carefully 1 Grading formula for the course 1 40 homework 2 30 quizes 3 30 final 2 Seven points a day late penalty 3 Collaboration Cheating Policy 1 You may NOT share written work 2 We reuse homework problems My Low Vision and You I have a genetic retinal condition called Stargardt s disease My central vision is going one pixel at a time to zero I have working peripheral vision I can t recognize faces so please introduce yourself to me every time I detect motion really well so please move your hand when you raise it in class Great Theoretical Ideas In Computer Science Steven Rudich Lecture 1 CS 15 251 Jan 13 2004 Spring 2004 Carnegie Mellon University Pancakes With A Problem The chef at our place is sloppy and when he prepares a stack of pancakes they come out all diferent sizes Therefore when I deliver them to a customer on the way to the table I rearrange them so that the smallest winds up on top and so on down to the largest at the bottom by grabbing several from the top and flipping them over repeating this varying the number I flip as many times as necessary Developing A Notation Turning pancakes into numbers Developing A Notation Turning pancakes into numbers 5 2 3 4 1 Developing A Notation Turning pancakes into numbers 5 2 3 4 1 Developing A Notation Turning pancakes into numbers 5 2 3 4 1 How do we sort this stack How many flips do we need 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 Algebraic Representation X The smallest number of flips required to sort X Lower Bound 5 2 3 4 1 Upper Bound Algebraic Representation X The smallest number of flips required to sort X 4 Lower Bound 5 2 3 4 1 Upper Bound 4 Flips Are Necessary 5 2 3 4 1 1 4 3 2 5 4 1 3 2 5 Flip 1 has to put 5 on bottom Flip 2 must bring 4 to top X 4 Lower Bound 4 X Lower Bound 4 Upper Bound X 4 5th Pancake Number P5 The number of flips required to sort the worst case stack of 5 pancakes P5 Lower Bound Upper Bound 5th Pancake Number P5 The number of flips required to sort the worst case stack of 5 pancakes 4 P5 Lower Bound Upper Bound The 5th Pancake Number The MAX of the X s 1 2 3 X1 X2 X3 5 2 3 4 1 4 1 9 9 X119 1 2 0 X120 P5 MAX over s2 stacks of 5 of MIN of flips to sort s 1 2 3 X1 X2 X3 5 2 3 4 1 4 1 9 9 X119 1 2 0 X120 Pn MAX over s2 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 Pn MAX over s2 stacks of n pancakes of MIN of flips to sort s Pn The number of flips required to sort a worst case stack of n pancakes Pn The number of flips required to sort a worst case stack of n pancakes Be Cool Learn Math speak 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 extra flip to handle the top two Hence P3 3 n Pancake Number th Pn The number of flips required to sort a worst case stack of n pancakes Pn Lower Bound Upper Bound Pn Take a few minutes to try and prove 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 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 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 Bring to top not always optimal for a particular stack 5 2 3 4 1 1 4 3 2 5 4 1 3 2 5 2 3 1 4 5 5 flips but can be done in 4 flips 3 2 1 4 5 Pn 2n 3 What bounds can you prove on Pn Breaking Apart Argument Suppose a stack S contains a pair of adjacent pancakes that will not be adjacent in the sorted stack Any sequence of flips that sorts stack S must involve one flip that inserts the spatula between that pair and breaks them apart 9 16 Breaking Apart Argument Suppose a stack S contains a pair of adjacent pancakes that will not be adjacent in the sorted stack Any sequence of flips that sorts stack S must involve one flip that inserts the spatula between that pair and breaks them apart Furthermore this same principle is true of the pair formed by the bottom pancake of S and the plate 9 16 n Pn Suppose n is even S contains n pairs that will need to be broken apart during any sequence that sorts stack S S 2 4 6 8 n 1 3 5 7 n 1 n Pn Suppose n is even S contains n pairs that will need to be broken apart during any sequence that sorts stack S Detail This construction only works when n 2 S 2 n Pn Suppose n is odd S contains n pairs that will need to be broken apart during any sequence that sorts stack S S 1 3 5 7 n 2 4 6 8 n 1 n Pn Suppose n is odd S contains n pairs that will need to be broken apart during any sequence that sorts stack S Detail This construction only works when n 3 S 1 …
View Full Document
Unlocking...