A. Complete exercise 9, part (a), from chapter 1 of the textbook (page 49 in the PDF). The algorithm can be given as an English explanation or in pseudocode similar to the book's notation. As requested, briefly explain the number of flips in the worst case. Note that because the algorithm runs in O(n) time, this will be some multiple of n.

Sorting 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?15 [Hint: This problem has nothing to do with the Tower of Hanoi.]