2 (Worth: 3 points. Page limit: 1 sheets; 2 sides) In a tribute to Dr. Seuss,! here is a question based on his story Yertle the turtle". You don't need to know the story to solve the question Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtles should be dispatched to form Yertle's throne. Each of the turtles ordered by Yertle has a different weight and strength Your task is to build the largest stack of turtles possible such that for every turtle in the stack, its strength is no less than the total weight that it carries above it. You are given as input the weight and the strength of each turtle. The strength is the turtle's overall carrying capacity, including its own weight. That is, a turtle weighing 300 units with a strength of 1000 units could carry other turtles weighing a total of 700 units on its back. Your algorithm should output the maximum number of turtles that can be stacked without exceeding the strength of any one. It should run in time O(n2), where n denotes the number of turtles given. You will be given partial credit for an algorithm that runs in time polynomial in n and the weights or strengths of the turtles Hint: Think about the order in which turtles should be stacked. Then try to come up with a recurrence that leads to an O(nW) time algorithm, where W is the total weight of all the turtles. Then think about how to change your recurrence to get a better running time. 2 (Worth: 3 points. Page limit: 1 sheets; 2 sides) In a tribute to Dr. Seuss,! here is a question based on his story Yertle the turtle". You don't need to know the story to solve the question Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtles should be dispatched to form Yertle's throne. Each of the turtles ordered by Yertle has a different weight and strength Your task is to build the largest stack of turtles possible such that for every turtle in the stack, its strength is no less than the total weight that it carries above it. You are given as input the weight and the strength of each turtle. The strength is the turtle's overall carrying capacity, including its own weight. That is, a turtle weighing 300 units with a strength of 1000 units could carry other turtles weighing a total of 700 units on its back. Your algorithm should output the maximum number of turtles that can be stacked without exceeding the strength of any one. It should run in time O(n2), where n denotes the number of turtles given. You will be given partial credit for an algorithm that runs in time polynomial in n and the weights or strengths of the turtles Hint: Think about the order in which turtles should be stacked. Then try to come up with a recurrence that leads to an O(nW) time algorithm, where W is the total weight of all the turtles. Then think about how to change your recurrence to get a better running time