Q1. Arrange the given order of magnitudes by its growth rate.

N, N2, N(logN), N(log

(logN), N(log2N), 2N+1, 307, N2(logN), N3, 2N . Indicate the functions grows at the same
rate.

Answer:

Q2. Arrange the following sequence of records in ascending order using external sorting (2-
way merge sort) 17, 3, 29, 56, 24, 18, 4, 9, 10, 23.
Q3. Given an array of integers 45, -33, 28, 19, 11, -77, 20, -52, arrange them in ascending
order using shell sort and display the order of elements and number of comparisons after
every iteration?

Answer:
Pass 1 : Interval = 4 No.of Sublist = 4 and No .of Camparison =4

Pass 2 : Interval = 2 No.Of Sublist = 2 and No.Of Camaprison = 12

Pass 3 : Interval = 1 Insertion Sort

Q4. Neha is interested in playing card game. She wants to arrange the cards in ascending
order with minimum number of comparisons and swaps. Help her by implementing a c
program with insertion sorting technique?

Answer:

#include<stdio.h>
void ShellSort(int a[], int n)
{
int i, j, increment, tmp;
for(increment = n/2; increment > 0; increment /= 2)
{
for(i = increment; i < n; i++)
{
tmp = a[i];
for(j = i; j >= increment; j -= increment)
{
if(tmp < a[j-increment])
a[j] = a[j-increment];
else
break;
}
a[j] = tmp;
}
}
}

int main()
{
int i, n, a[10];
printf("Enter the number of elements :: ");
scanf("%d",&n);
printf("Enter the elements :: ");
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
ShellSort(a,n);
printf("The sorted elements are :: ");
 for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}

Q5. Mr. Darvin is working as a full-time scholar in IIT Bombay. He is doing research on
quick sort with given numbers and completed the first iteration successfully by placing first
pivot element in correct position. Suddenly, he went for shopping along with his wife and
left the sequence as it is [ 212, -25, 221, 122, 512, 978, 521, 876, 768]. His daughter Alexa
seen the sequence and she is trying to arrange them in sorted order. Help Alexa to find the
first pivot element which is placed by Darwin and trace the sequence to arrange the
numbers in ascending order accordingly.

Answer:
In the above problem the input is [ 212, -25, 221, 122, 512, 978, 521, 876, 768],

the middle element is being chosen as pivot i.e. 512. After first iteration, all elements lesser than
it are moved to left and greater than it are moved to it's right.

Quick Sort Algorithm 2M

1. Choose an item p (known as the pivot)

2. Then partition the items of a[i..j] into three parts: a[i..m-1], a[m], and a[m+1..j].
3. a[i..m-1] (possibly empty) contains items that are smaller than (or equal to) p.
4. a[m] = p, i.e., index m is the correct position for p in the sorted order of array a.
5. a[m+1..j] (possibly empty) contains items that are greater than (or equal to) p.
6. Then, recursively sort the two parts.
Tracing:
 Q6. In Indian Army batch number 32567IN captain Mahesh wants to arrange his corps in
ascending order according to the corps height. Initially he divided all the soldiers into team
Alpha and team Beta. After dividing into two teams, he realized that team Beta corps are
stood in height wise. So, help the captain Mahesh to arrange the team Alpha corps in
height wise by implementing merge sort and show the time taken to arrange them in
ascending order?

Answer:
void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;
int LeftArray[n1], RightArray[n2]; //temporary arrays
for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i]; //copy data to temp arrays
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j]; // copy data to temp arrays
i = 0;
j = 0;
k = beg;
while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}
while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
 }
}
void mergeSort(int a[], int beg, int end)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
void Result(int a[], int n) // Display the result
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main()
{
int a[100] ,i,n;
printf(“ Enter the size of corps “);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(“ \n Enter the height of corps member \n“);
scanf(“%d”,&a[i]);
}
printf(" Before Arranging \n");
Result(a, n);
mergeSort(a, 0, (0+n-1)/2);
printf ("After Arranging \n");
Result(a, n);
}

Time Complexity:

T(N) = Time Complexity for problem size N

T(n) = Θ(1) + 2T(n/2) + Θ(n) + Θ(1)
T(n) = 2T(n/2) + Θ(n)
Let us analyze this step by step:
T (n) = 2 * T (n/2) + 0(n)
STEP-1 Is to divide the array into two parts of equal size.
2 * T (n/2) --> Part 1
STEP-2 Now to merge basically traverse through all the elements.
Constant * n --> Part 2
STEP-3 --> COMBINE 1 + 2
T (n) = 2 * T (n/2) + constant * n --> Part 3
Now we can further divide the array into two half’s if size of the partition arrays are greater than
1. So,
N/2/2--> n/4
T (N) = 2 * (2 * T (n/4) + constant * n/2) + constant * n
T (N) = 4 * T (n/4) + 2 * constant * n
For this we can say that:
Where n can be substituted to 2^k and the value of k is logN
T (n) = 2^k * T (n/ (2^k)) + k * constant * n
Hence,
T (N) = N * T (1) + N *( log N)
= O(N * log(N))

Q7. write a function to dequeue an element from the priority queue?

Answer:

void dequeue()
{
struct Queue *ptr;
if(front==NULL) // queue is empty
{
printf("Queue is empty\n");
}
else if(front==rear) // queue is with single node
{
ptr = front;
front = NULL;
rear = NULL;
printf("Dequeued node is %d\n", ptr->data);
free(ptr);
}
else // queue with multiple nodes

{
ptr = front;
front = front->next;
ptr->next = NULL;
printf("Dequeued node is %d\n", ptr->data);
free(ptr);
}
display();
}

Q8. Write a function to insert an element into circular queue?

Answer:

void enqueue()
{
int key;
printf("\nEnter element\n");
scanf("%d", &key);

if(r==SIZE-1&&f==0 || r==f-1)
{
printf("\nQueue overflow\n");
}
else if(f==-1 && r==-1)
{
f = f+1;
r = r+1;
queue[r] = key;
}
else if(r==SIZE-1 && f>0)
{
r = 0;
queue[r] = key;
}
else
{
r = r+1;
queue[r] = key;
}
display();
}

Q9. Display the final popped out element in given scenario, If the seven elements A, B, C,
D, E, F and G are pushed into a stack in reverse order, i.e., starting from G. The stack is
popped five times and each element is inserted into a queue. Then two elements are
dequeued from the queue and pushed back into the stack. Now, one element is popped
from the stack.

Answer:
The final popped out element is B.

Q10. Write a C program to implement the following operations on doubly linked list?
a. Give the node structure
b. Delete an element at the given position
c. Insert an element at the given position

Answer:

a. Give the node structure

struct Node
{
struct Node *prev;
int data;
struct Node *next;
};
struct Node *head = NULL;

b. Delete an element at the given position

void deleteAtPosition(int pos)
{
int cnt , i;
struct Node *ptr, *ptr1, *ptr2;
cnt = countList();

if(pos>=0 && pos<=cnt)

{
if(head==NULL) // listy is empty
{
printf("List is empty\n");
}
else if(head->next==NULL && pos==0) // list is with one node
{
ptr = head;
head = NULL;
printf("Deleted node is %d\n", ptr->data);
free(ptr);
}
else if(head->next!=NULL && pos==0) // list is with multiple nodes
{ // position is zero
ptr = head;
head = head->next;
ptr->next = NULL;
head->prev = NULL;
printf("Deleted node is %d\n", ptr->data);
free(ptr);
}
else
{
ptr = head;
for(i=0; i<pos-1; i=i+1)
{
ptr = ptr->next;
}
ptr1 = ptr->next;
ptr2 = ptr1->next;
if(ptr2!=NULL)
{
ptr->next = ptr2;
ptr2->prev = ptr;
ptr1->next = NULL;
 ptr1->prev = NULL;
}
else
{
ptr->next = NULL;
ptr1->prev = NULL;
}
printf("Deleted node is %d\n", ptr1->data);
free(ptr1);
}
display();
}
else
{
printf("Not possible to delete\n");
}
}

c. Insert an element at the given position

void insertAtPosition()
{
int pos, cnt, i;
struct Node *newNode = createNode(), *ptr, *ptr1;
cnt = countList();
printf("Enter position\n");
scanf("%d", &pos);

if(pos>=0 && pos<=cnt)

{
if(cnt==0 && pos==0) // list is empty
{
head = newNode;
}
else if(cnt!=0 && pos==0)
{
newNode->next = head;
head->prev = newNode;
head = newNode;
}
else
{
ptr = head;
for(i=0; i<pos-1; i=i+1)
{
ptr = ptr->next;
}
 ptr1 = ptr->next;
newNode->prev = ptr;
newNode->next = ptr1;
ptr->next = newNode;
ptr1->prev = newNode;
}
printf("Node is inserted\n");
display();
}
else
{
printf("Not possible to inseet\n");
}
}

Q11. Wrote a C program to convert the given infix expression into postfix expression. And
trace that program by converting the given infix expression (a +b) * (c – ((d ^ e) ^ f)) into
postfix expression. Assume that the operators +, -, × are left associative and ^ is
right associative. The order of precedence (from highest to lowest) is ^, x, +, -.

Answer:
Program:

#include<stdio.h>

#include<ctype.h>

char stack[100];

int top=-1;

void push(char ch)

top++;

stack[top]=ch;

char pop()

if(top == -1)
 return -1;

else

return stack[top--];

int priority(char ch)

if(ch == '^')

return 3;

else if(ch == '*' || ch == '/')

return 2;

else if(ch == '+' || ch == '-')

return 1;

else

return 0;

void convertPost(char ch[])

for(int i=0;ch[i]!='\0';i++)

if(isalnum(ch[i]))

printf("%c",ch[i]);

else if(ch[i] == '(')

push(ch[i]);

else if(ch[i] == ')')

{
 char x;

while((x = pop()) != '(')

printf("%c",x);

else

while(priority(stack[top]) >= priority(ch[i]))

printf("%c",pop());

push(ch[i]);

while(top != -1)/* bring all the remaining elements of stack*/

printf("%c",pop());

int main()

char inputEx[100];

printf("enter the infix expression");

scanf("%s",inputEx);
 convertPost(inputEx);

return 0;

Program tracing and conversion of infix to postfix

Infix Stack Postfix

( (
A ( a
+ (+ a
B (+ ab
) (+) ab+
* * ab+
( *( ab+
c *( ab+c
- *(- ab+c
( *(-( ab+c
( *(-(( ab+c
d *(-(( ab+cd
^ *(-((^ ab+cd
e *(-((^ ab+cde
) *(-((^) ab+cde^
^ *(-(^ ab+cde^
f *(-(^ ab+cde^f
) *(-(^) ab+cde^f^
) *(-) ab+cde^f^-
ab+cde^f^-*

Postfix expression is ab+cde^f^-*

Q12. Mr. Rajesh is CEO of an organization ‘Software Solutions’. He wants to maintain the
personal information of his employee’s like Ename (Employee Name), Eno (Employee Number),
and salary using singly linked list. So, help him to store and organize the data with following
operations.
a. Write a function to read and maintain employee data
b. Write a function that reads Eno (Employee Number) and then increase 10% salary.
c. Write a function that reads Ename (Employee Name), search and display the employee
details.

Answer:
#include<stdio.h>

#include<string.h>

#include<stdlib.h>

void create();

void per();

void search();

void Display();

void per();

typedef struct Node

char name[100];

long int num;

int salary;

struct Node *next;

}s;

s *head=NULL,*tail=NULL,*p,*q,*k;

void main()

int opt;

do{

printf("enter your option\n");

scanf("%d",&opt);

switch(opt)

{
 case 1:

create();

break;

case 2:

per();

break;

case 3:

search();

break;

case 4:

Display();

break;

}while(opt>=1&&opt<=4);

void create()

int x,n,i;

char N[100];

long int Eno;

int sal;

printf("enter no of nodes\n");

scanf("%d",&n);

for(i=1;i<=n;i++)

{
 p=(s*)malloc(sizeof(s));

fflush(stdin);

printf("enter name\n");

scanf("%s",N);

strcpy(p->name,N);

printf("enter id no\n");

scanf("%ld",&Eno);

p->num=Eno;

printf("enter salary\n");

scanf("%d",&sal);

p->salary=sal;

p->next=NULL;

if(i==1)

head=tail=p;

else

tail->next=p;

tail=p;

void Display()

if(head==NULL)
 printf("list is empty\n");

else

for(p=head;p!=NULL;p=p->next)

printf("%s\n",p->name);

printf("%ld\n",p->num);

printf("%d\n",p->salary);

void per()

long int ino;

int z;

printf("enter idno\n");

scanf("%ld",&ino);

p=head;

while((p->num)!=ino)

p=p->next;

z=(p->salary)+(p->salary*10)/100;

printf("%d",z);
}

void search()

int flag=0;

char search[100];

printf("enter search value\n");

scanf("%s",search);

for(p=head;p!=NULL;p=p->next)

if(strcmp(p->name,search)==0)

flag=1;

break;

if(flag==1)

printf("name found");

else

printf("name not found ");