Question 1: A palindrome is a word (sequence of characters) that reads the same

Question

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

Explanation / Answer

Question 1:

Illustrate a word / string is Palindrome Using Stacks

Pre-Requistive: Input String is Needed from End-User

Code is Stated Below:

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define SIZE 30

int t=-1,f=0; /* t is top and f is for front of the Stack */

int s[SIZE]; //holds the MAX SIZE of the String to be passed on

void push(char); //insert char to the stack

void pop(); //delete from stack

void main()

{

int i;

char s1[SIZE], b;

printf("Enter the String to be Verified for Palindrome ");

scanf("%s",s1);

for(i = 0;s1[i] != '';i++) //loop y until NULL Termination String

{

b=s1[i];

push(b);

}

for(i=0;i<(strlen(s1) / 2 );i++)

{

if(s[t] == s[f])

{

pop();

f++;

}

else

{

printf("Entered String %s is Not a palindrome",s1);

}

}

if((strlen(s1) / 2) == f)

{

printf("Enter String %s is Palindrome",s1);

}

f = 0;

t = -1;

}

void push(char a)

{

t++;

s[t] = a;

}

void pop()

{

t--;

}

Question 2:

Algorithm to be derived for power(a,n) , Divide and ConQuer Algorithm Is the Ideal Algorithm Paradigm,

Time Complexity to be derived as O(n) (Without Optimization ) But in the Code Pasted in Question 2 Optimization of power (a, n/4) is used So Time Complexity of Optimized Solution Could be O(logn), This makes the function to be optimized and used efficitely.

Space Complexity to be derived as O(1)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.