9. Suppose you are given a stack of n pancakes of different sizes. You want to sort the pancakes so that smaller pancakes are on top of larger pancakes. The only operation you can perform is a flip-insert a spatula under the top k pancakes, for some integer k between 1 and n, and flip them all over. Figure 1.19. Flipping the top four pancakes (a) Describe an algorithm to sort an arbitrary stack of n pancakes using O(n) flips. Exactly how many flips does your algorithm perform in the worst case? (Hint: This problem has nothing to do with the Tower of Hanoi.) "The exact worst case optimal number of flips required to sort n pancakes (either burned or unburned) is an long-standing open problem; just do the best you can 49 b and a 1. RECURSION (b) For every positive integer n, describe a stack of n pancakes that requires n(n) flips to sort. (c) 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