(V) (35 points) In the data structure queue, elements can be added to one end and removed from the other. Different from queues, a deque allows elements to be added to and removed from both ends (a) (15 points) Given a deque with a permutation of the numbers from 1 to n (n>5), we want to remove all of the numbers to form a sequence that maximizes the alternative sum (at-a2 + ?? t a), where a is the first number removed, a2 is the second number, and so on. For example, suppose a deque contains 5 numbers as follows (head) 2, 3, 1, 4, 5 (rear) One possible generated sequence is whose alternative sum is 9 (1) (6 points) Give an example to demonstrate that the problem cannot be solved by a greedy algorithnm, which first removes the larger one of the two ends, then removing in the order of the smaller one, the larger one, the smaller one, etc. Show your calculation (2) (10 points) Devise an O(n2) algorithm to generate the optimal sequence for a given deque. Explain how your algorithm works on the example you give previously (b) (20 points) Stacks can be used to implement queues and deques (1) (6 points) Describe how to implement a queue using only two stacks. And then describe how to extend (2) (7 points) Use the accounting method to prove the amortized time complexity ofa sequence ofn queue (3) (7 points) Prove or disprove that the amortized time complexity of a sequence of n deque operations the way to implement a queue to implement a deque using the same two stacks operations (implemented with stacks) is O(n). Show your derivation. (implemented with stacks) is also O(n). Show your derivation. (V) (35 points) In the data structure queue, elements can be added to one end and removed from the other. Different from queues, a deque allows elements to be added to and removed from both ends (a) (15 points) Given a deque with a permutation of the numbers from 1 to n (n>5), we want to remove all of the numbers to form a sequence that maximizes the alternative sum (at-a2 + ?? t a), where a is the first number removed, a2 is the second number, and so on. For example, suppose a deque contains 5 numbers as follows (head) 2, 3, 1, 4, 5 (rear) One possible generated sequence is whose alternative sum is 9 (1) (6 points) Give an example to demonstrate that the problem cannot be solved by a greedy algorithnm, which first removes the larger one of the two ends, then removing in the order of the smaller one, the larger one, the smaller one, etc. Show your calculation (2) (10 points) Devise an O(n2) algorithm to generate the optimal sequence for a given deque. Explain how your algorithm works on the example you give previously (b) (20 points) Stacks can be used to implement queues and deques (1) (6 points) Describe how to implement a queue using only two stacks. And then describe how to extend (2) (7 points) Use the accounting method to prove the amortized time complexity ofa sequence ofn queue (3) (7 points) Prove or disprove that the amortized time complexity of a sequence of n deque operations the way to implement a queue to implement a deque using the same two stacks operations (implemented with stacks) is O(n). Show your derivation. (implemented with stacks) is also O(n). Show your derivation