ALL QUESTIONS ARE IN THE SQUARE BOXES. REST ARE PARAGRAPHS DESCRIBING HOW TO SOLVE THE QUESTIONS

1 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. . . . nl store the pancakes on the plate created by the bad cook. In particular, Plj] refers to the jth pancake from the top. Thus, for n-5 the input array can look like this: P-3,2,4,-1,-5] Let flip(i), 1 i n, be the operation where the entries of Pis modified as -Pi, -Pi, -P.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 P into the array 1,2,,n using flip operations only. a. Describe a sequence of flips that tranforms P-3,2,4,-1,-5] into 1,2,3,4, 5 b. Design an algorithmthat transforms an input P of n pancakes arbitrarily arranged into1,2,. , n using flip operations only c. How much time does it take to implement flipi)? 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 al gorithm? 2. Combining lists. Let Land L' be two LIST ADT's whose elements are sorted in increasing order. For our purposes, the elements are numbers but they can be names, for example, arranged in alphabetical order. Assume that a doubly linked list was used to implement a LIST ADT a. Given L and L', we are interested in combining L and L' into one single LIST ADT where the elements are still in sorted order. In particular, if e is in L or L', e should appear in the output exactly once. For example, suppose the sequence of numbers in L and L' are (3, 5,6,7) and (2,3,8,9,10) respectively, the output should contain the sequence (2,3,5,6,7,8,9.10) Suppose L has n elements and L' has m elements. Describe an algorithm that ac complishes the task described above in O(nm) time. b. Let us call your algorithm in part (a) UNION(L, L'.Suppose we now have K LUST ADT's Li , La . . . 4 whose elements are in sorted order. This time we want to combine all of them into a single LIST ADT where the elements are again in sorted order. Like before, an element that is in any L, must appear in the output exactly once. Let D be an ADT that contains the values L.first fori1,....k. Then we can combine the lists as ollows: function CoMBINE(D) while D.size 2 2 do remove L.first and L'.first from D add UNION(L, L'.first to D end while return the only element L.first in D end function b1. Assume that L... L all haven elements. If D is a stack, what is the running time of COMBINE(D)? Your answer should be in terms of n and k(i.e., don't treat k as a constant.) b2. What if D is a queue? That is, what is the running time of COMBINE(D)? 3. Inorder traversals. Suppose T is a BinaryTree ADT. Assume, as the book does, that T is a proper binary tree. That is, if v is an internal node, then e has a left and a right child Design algorithms for the following methods: inorderBefore(v): returns the node processed before v in an inorder traversal of T. inorderNext (v): returns the node processed after v in an inorder traversal of 7T Explain why your algorithms are correct and determine their running times. For example, consider the binary tree in Figure 2.34 of your book. Let vbe the left child of the root node (the one containing "and labeled '2'). Then inorderBefore() returns the node containing 3 and labeled '9' while inorderNext (v) returns the node containing 9 and labeled '20' Note: Your answer should not involve running an inorder traversal of T. Rather, you should start with v and then determine the nodes that are visited before or after it. 1 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. . . . nl store the pancakes on the plate created by the bad cook. In particular, Plj] refers to the jth pancake from the top. Thus, for n-5 the input array can look like this: P-3,2,4,-1,-5] Let flip(i), 1 i n, be the operation where the entries of Pis modified as -Pi, -Pi, -P.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 P into the array 1,2,,n using flip operations only. a. Describe a sequence of flips that tranforms P-3,2,4,-1,-5] into 1,2,3,4, 5 b. Design an algorithmthat transforms an input P of n pancakes arbitrarily arranged into1,2,. , n using flip operations only c. How much time does it take to implement flipi)? 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 al gorithm? 2. Combining lists. Let Land L' be two LIST ADT's whose elements are sorted in increasing order. For our purposes, the elements are numbers but they can be names, for example, arranged in alphabetical order. Assume that a doubly linked list was used to implement a LIST ADT a. Given L and L', we are interested in combining L and L' into one single LIST ADT where the elements are still in sorted order. In particular, if e is in L or L', e should appear in the output exactly once. For example, suppose the sequence of numbers in L and L' are (3, 5,6,7) and (2,3,8,9,10) respectively, the output should contain the sequence (2,3,5,6,7,8,9.10) Suppose L has n elements and L' has m elements. Describe an algorithm that ac complishes the task described above in O(nm) time. b. Let us call your algorithm in part (a) UNION(L, L'.Suppose we now have K LUST ADT's Li , La . . . 4 whose elements are in sorted order. This time we want to combine all of them into a single LIST ADT where the elements are again in sorted order. Like before, an element that is in any L, must appear in the output exactly once. Let D be an ADT that contains the values L.first fori1,....k. Then we can combine the lists as ollows: function CoMBINE(D) while D.size 2 2 do remove L.first and L'.first from D add UNION(L, L'.first to D end while return the only element L.first in D end function b1. Assume that L... L all haven elements. If D is a stack, what is the running time of COMBINE(D)? Your answer should be in terms of n and k(i.e., don't treat k as a constant.) b2. What if D is a queue? That is, what is the running time of COMBINE(D)? 3. Inorder traversals. Suppose T is a BinaryTree ADT. Assume, as the book does, that T is a proper binary tree. That is, if v is an internal node, then e has a left and a right child Design algorithms for the following methods: inorderBefore(v): returns the node processed before v in an inorder traversal of T. inorderNext (v): returns the node processed after v in an inorder traversal of 7T Explain why your algorithms are correct and determine their running times. For example, consider the binary tree in Figure 2.34 of your book. Let vbe the left child of the root node (the one containing "and labeled '2'). Then inorderBefore() returns the node containing 3 and labeled '9' while inorderNext (v) returns the node containing 9 and labeled '20' Note: Your answer should not involve running an inorder traversal of T. Rather, you should start with v and then determine the nodes that are visited before or after it