Q1: write code in c++ for the three different data structures

Q2: do all parts, a,b, and c

Question 1: A palindrome is a word (sequence of characters) that reads the same backward as forward (e.g. civic, refer). Write the most efficient algorithm (one for each data structure) to check if a word w is a palindrome by using: a.Stacks b.Queues c.Deques a queue with the sequence of characters in For each data structure, your input is instance, for the word "hello" the input of your algorithm is a queue: (front) h, e, I, I, o (rear). If you need to duplicate the input queue or any other container (stack, queue, deque) you can use an operation duplicate(container) that runs in O(n) and returns a replica of the given container. the word. For Specify and justify your choice of implementation for each ADT being used (static array incremental/doubling growable array, singly linked list, doubly linked list). Show the overall cost of your three algorithms and justify your answer. What is the best data structure among those three to solve the problem? Explain why based on time and space costs. Question 2: For the algorithm below, do the time analysis (count the lines in red) by: (a) finding the recursive cost function; (b) solving it (closed form); (c) showing the simplest order of growth (big oh) for the cost function. Consider that n is a power of 4, i.e., n-4, for a natural k> 0. A1gorithm power(a,n) Input: a > 0, n0 (naturals) Output an if nm 1 then return a; R power(a, n/4); return R*RR R Question 1: A palindrome is a word (sequence of characters) that reads the same backward as forward (e.g. civic, refer). Write the most efficient algorithm (one for each data structure) to check if a word w is a palindrome by using: a.Stacks b.Queues c.Deques a queue with the sequence of characters in For each data structure, your input is instance, for the word "hello" the input of your algorithm is a queue: (front) h, e, I, I, o (rear). If you need to duplicate the input queue or any other container (stack, queue, deque) you can use an operation duplicate(container) that runs in O(n) and returns a replica of the given container. the word. For Specify and justify your choice of implementation for each ADT being used (static array incremental/doubling growable array, singly linked list, doubly linked list). Show the overall cost of your three algorithms and justify your answer. What is the best data structure among those three to solve the problem? Explain why based on time and space costs. Question 2: For the algorithm below, do the time analysis (count the lines in red) by: (a) finding the recursive cost function; (b) solving it (closed form); (c) showing the simplest order of growth (big oh) for the cost function. Consider that n is a power of 4, i.e., n-4, for a natural k> 0. A1gorithm power(a,n) Input: a > 0, n0 (naturals) Output an if nm 1 then return a; R power(a, n/4); return R*RR R