Ask Question
21 September, 01:59

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. 21 September, 04:23
    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?
Get 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 there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers