Scribd Logo
Upload

Welcome to Scribd!

  • 29 views

    Lecture 01

    Uploaded by

    James Yang
    sd

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Lecture 01

    Uploaded by

    James Yang
    29 views11 pages
    sd

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    sd

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    29 views11 pages

    Lecture 01

    Uploaded by

    James Yang
    sd

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 11

    15-251

    Cooking for Computer Scientists

    15-251 Course Evaluations: Student Comments


    sadistic 251 is like: were gonna kick your ass and youre gonna enjoy it. And we did! Von Ahn mocked Intelligent Design in one of the first lectures, which deeply offended me

    Some Great Theoretical Ideas in Computer Science for www.cs.cmu.edu/~15251

    15-251

    Course Staff
    Instructors
    Ryan ODonnell Steven Rudich Luis von Ahn

    TAs
    Cory Chang Asa Frank Kyle Griswold Yuyang Guo Kevin Rawlings Sang Tian (head) Pranab Senthilnathan Kevin Zhang

    Grading
    Raw Grade = 0.28!HW + 0.35!MIDTERMS + 0.30!FINAL + 0.05!QUIZES + 0.02!PARTICIPATION MIDTERMS = 0.4THIGHEST + 0.4TMIDDLE + 0.2TLOWEST Lowest homework grade and lowest quiz grade are dropped Letter Grade = CURVE(Raw Grade) We only curve up!

    Dear Professor, I know my grade is a 22/100, and according to the class Web site that is an F. Is there an alternative grading scheme by which I can get a C?

    Dear <NAME>, As a matter of fact, there are infinitely many alternative grading schemes by which you would get a C with a 22/100. Unfortunately for you, I will not use any of them.

    Homework
    Weekly homework is the bread an butter of this class You have a total of 5 late days for the semester. No more than 3 can be used on any one homework. No homework will be accepted more than three days late Homework MUST be typeset

    Collaboration + Cheating
    You may NOT share written work You may NOT use Google, or solutions to previous years homework You MUST sign the class honor code

    (((

    )))

    Feel free to ask questions

    ! "

    I understand that making pancakes can be a dangerous activity and that, by doing so, I am taking a risk that I may be injured. I hereby assume all the risk described above, even if Luis von Ahn, his TAs or agents, through negligence or otherwise, otherwise be deemed liable. I hereby release, waive, discharge covenant not to sue Luis von Ahn, his TAs or any agents, participants, sponsoring agencies, sponsors, or others associated with the event, and, if applicable, owners of premises used to conduct the pancake cooking event, from any and all liability arising out of my participation, even if the liability arises out of negligence that may not be foreseeable at this time. Please dont burn yourself

    Pancakes With A Problem!


    Lecture 1 (January 15, 2013)

    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

    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


    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

    Four Flips Are Necessary


    5 2 3 4 1 1 4 3 2 5 4 1 3 2 5

    ? ! X !4 ?
    Upper Bound

    If we could do it in three flips: Flip 1 has to put 5 on bottom Flip 2 must bring 4 to top (if it didnt, we would spend more than 3)

    4!X!4
    Lower Bound Upper Bound

    5th Pancake Number


    Number of flips required to sort the P5P = 5 = MAX over s 2 stacks of 5 worst case # stack of 5 pancakes of MIN of flips to sort s
    1 2 1 3 4 5 5 4 2 3 2 1

    X=4

    ...

    5 2 3 4 1

    ...

    1 1 9

    1 2 0

    X1

    X2

    X3

    X119

    X120

    5th Pancake Number


    Lower Bound

    4 ? ! P5 ! ?
    Upper Bound

    Pn = Pn =

    MAX over sstacks of n pancakes of MIN # of flips to sort s 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 Pn 0 0 1 0 2 1 3 3

    P3 = 3
    1 3 2 requires 3 Flips, hence P3 # 3

    nth Pancake Number


    Pn =
    Number of flips required to sort the worst case stack of n pancakes

    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

    Lower Bound

    ? ! Pn ! ?
    Upper Bound

    Bracketing:
    What are the best lower and upper bounds that I can prove?

    ? ! Pn ! ?
    Try to find upper and lower bounds on Pn, for n > 3

    ! f(x) !

    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

    ? ! Pn ! 2n-3

    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 3 2 1 4 5

    ? ! Pn ! 2n-3
    What other bounds can you prove on Pn?

    Bring-to-top takes 5 flips, but we can do in 4 flips

    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

    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

    16

    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

    n ! Pn ! 2n 3 for n > 3
    Bring-to-top is within a factor of 2 of optimal! 1 3 2

    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 1,2,3,4,5 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 T: 5,2,4,3,1 3,5,1,2,4

    The Known Pancake Numbers


    n 1 2 3 4 5 6 7 8 9 10 11 12 13 Pn 0 1 3 4 5 7 8 9 10 11 13 14 15

    Is This Really Computer Science?

    P14 is Unknown
    1!2!3!4!!13!14 = 14! orderings of 14 pancakes

    14! = 87,178,291,200

    Sorting By Prefix Reversal

    (17/16)n ! Pn ! (5n+5)/3
    William Gates and Christos Papadimitriou. Bounds For Sorting By Prefix Reversal. Discrete Mathematics, vol 27, pp 47-57, 1979.

    Posed in Amer. Math. Monthly 82 (1) (1975), Harry Dweighter a.k.a. Jacob Goodman

    (15/14)n ! Pn ! (5n+5)/3
    H. Heydari and H. I. Sudborough. On the Diameter of the Pancake Network. Journal of Algorithms, vol 25, pp 67-94, 1997.

    How many different stacks of n pancakes are there? n! = 1 x 2 x 3 x x n

    Pancake Network: Definition For n! Nodes


    For each node, assign it the name of one of the n! stacks of n pancakes Put a wire between two nodes if they are one flip apart

    Network For n = 3
    1 2 3 2 1 3 3 1 2

    3 2 1

    2 3 1

    1 3 2

    Network For n=4

    Pancake Network: Message Routing Delay


    What is the maximum distance between two nodes in the pancake network?

    Pn

    Pancake Network: Reliability


    If up to n-2 nodes get hit by lightning, the network remains connected, even though each node is connected to only n-1 others The Pancake Network is optimally reliable for its number of edges and nodes

    Mutation Distance

    10

    One Simple Problem


    A host of problems and applications at the frontiers of science

    High Level Point


    Computer Science is not merely about computers and programming, it is about mathematically modeling our world, and about finding better and better ways to solve problems Todays lecture is a microcosm of this exercise

    Definitions of: nth pancake number lower bound upper bound Proof of: ANY to ANY in " Pn Heres What You Need to Know Important Technique: Bracketing

    11

    You might also like