Ask Question
4 January, 15:28

Now suppose one side of each pancake is burned. Describe an algorithm to sort an arbitrary stack of n pancakes, so that the burned side of every pancake is facing down, using O (n) flips. Exactly how many flips does your algorithm perform in the worst case

+4
Answers (1)
  1. 4 January, 15:49
    0
    B. F. (P[1 ... n])

    for i n down to 2

    k position of the ith smallest pancake

    F (k) / /Flip it to the top, if the top pancake's burned side is down

    F (1)

    F (i) / /Flip it into place, if the top pancake's burned side is up

    F (1)

    The algorithm uses at most 3n-2 flips in the worst case

    Explanation:

    Whenever each pancake reaches the top of the stack, it will be flipped, if necessary to ensure that its burned side is up, so that whenever it is flipped down to its proper place, its burned side is down
Know the Answer?
Not Sure About the Answer?
Find an answer to your question 👍 “Now suppose one side of each pancake is burned. Describe an algorithm to sort an arbitrary stack of n pancakes, so that the burned side of ...” in 📗 Engineering if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers