3. (5 pts.) Pancake aesthetics. A diner serves a breakfast plate which simply consists of n pancakes. A very bad cook fills the order. He proceeds by making n pancakes-all of different sizes and all with one side burnt. He then piles the pancakes onto a plate to create a tower of pancakes. Mr. Waiter picks up the plate and immediately realizes that he has to make the plate presentable. He wants to (i) sort the pancakes from smallest to largest with the largest pancake at the bottom of the plate, and (ii) hide the burnt side of each pancake. Now he only has one move available to him - push a spatula underneath one of the pancakes and then flip the entire subtower of pancakes above the spatula upside down. His goal is to use this move repeatedly until his goals are accomplished. How many moves does he need? Let's create a mathematical model for this problem. Represent the ith smallest pancake as i if the pancake has its good side facing up and as i if its burnt side is facing up. Let the array P[1,...n] store the pancakes on the plate created by the bad cook. In particular, P[j] refers to the th pancake from the top. Thus, for n = 5 the input array can look like this: P=1-3,2,4,-1,-5). Let flip(i), 1 sis n, be the operation where the entries of P[1... i) is modified as [-P[i], P[i 1),..., P[1]]. For example, if we apply flip(3) to the above example, the results is (-4, -2,3,-1, -5]. Our goal is to transform the input Pinto the array [1, 2,..., n] using flip operations only. = (-3, 2, 4,-1,-5) into a. (1 pt.) Describe a sequence of flips that tranforms P [1, 2, 3, 4, 5). b. (2 pts.) Design an algorithm (i.e., write a pseudocode) that transforms an input P of n pancakes arbitrarily arranged into [1,2,..., n] using flip operations only. c. (1 pt.) Write a pseudocode that implements flip(i). d. (1 pt.) How much time does it take to implement flip(i)? In the worst case, how many flips will your algorithm perform? Based on your answers to these two questions, what is the running time of your algorithm? All your answers should be in terms of the Big-Oh notation. 3. (5 pts.) Pancake aesthetics. A diner serves a breakfast plate which simply consists of n pancakes. A very bad cook fills the order. He proceeds by making n pancakes-all of different sizes and all with one side burnt. He then piles the pancakes onto a plate to create a tower of pancakes. Mr. Waiter picks up the plate and immediately realizes that he has to make the plate presentable. He wants to (i) sort the pancakes from smallest to largest with the largest pancake at the bottom of the plate, and (ii) hide the burnt side of each pancake. Now he only has one move available to him - push a spatula underneath one of the pancakes and then flip the entire subtower of pancakes above the spatula upside down. His goal is to use this move repeatedly until his goals are accomplished. How many moves does he need? Let's create a mathematical model for this problem. Represent the ith smallest pancake as i if the pancake has its good side facing up and as i if its burnt side is facing up. Let the array P[1,...n] store the pancakes on the plate created by the bad cook. In particular, P[j] refers to the th pancake from the top. Thus, for n = 5 the input array can look like this: P=1-3,2,4,-1,-5). Let flip(i), 1 sis n, be the operation where the entries of P[1... i) is modified as [-P[i], P[i 1),..., P[1]]. For example, if we apply flip(3) to the above example, the results is (-4, -2,3,-1, -5]. Our goal is to transform the input Pinto the array [1, 2,..., n] using flip operations only. = (-3, 2, 4,-1,-5) into a. (1 pt.) Describe a sequence of flips that tranforms P [1, 2, 3, 4, 5). b. (2 pts.) Design an algorithm (i.e., write a pseudocode) that transforms an input P of n pancakes arbitrarily arranged into [1,2,..., n] using flip operations only. c. (1 pt.) Write a pseudocode that implements flip(i). d. (1 pt.) How much time does it take to implement flip(i)? In the worst case, how many flips will your algorithm perform? Based on your answers to these two questions, what is the running time of your algorithm? All your answers should be in terms of the Big-Oh notation