ASSIGNMENT- DATA STRUCTURES USING C

NAME- SULTHAN NOUSHAD AUD21703

1) E.NO: A40105223013

a) Analyze the differences between time complexity and space complexity in

algorithm design. Provide examples to support your answer. Develop an algorithm
to implement a sparse matrix and discuss its advantages
Time complexity Space complexity
It refers to the amount of time taken by It refers to the amount of memory taken
the algorithm to run and produce the by the algorithm to run and produce the
desired output. desired output.

It can be represented using big O It can be also represented using big O

notation. notation.

For loops that iterate n times →O(n) Space complexity depends on the
For nested loops that iterate n times → datatypes and structures chosen, For eg.
O(n2) int, float char are O(1), memory allocated
variables are of O(n)

Example- Quicksort has average time- It has a space complexity of O(logn).

complexity of O(nlogn)

Pseudocode for sparse matrice

int im[50][50], spm[100]->EMPTY, count=0, tri[3],r,c
FOR i=0 TO r-1
FOR j=0 TO c-1
IF im[i][j]!=0
tri[0]=i
tri[1]=j
tri[2]=im[i][j]
spm[count]=tri
count++

Advantages of sparse matrices

• Reduced consumption of resources by only storing non-zero elements
• Better performance because of fast matrix operations on non-zero elements and
hence reduces computational overhead
• Can handle large datasets efficiently
b) Design a C program to implement character string operations like
concatenation, reversal, and comparison. Discuss how arrays can be used to
manage such operations effectively.
#include <stdio.h>
#include <stdlib.h>
int i;
void concat(char s[100],char t[100])
{
int i,j;
for (i=0;s[i]!='\0';i++);
for(j=0;t[j]!='\0';j++,i++)
{
s[i]=t[j];
}
s[i]='\0';
}
void cmp(char s[100],char t[100])
{
int len1=0,len2=0;
for (i=0;s[i]!='\0';i++,len1++);
for (i=0;t[i]!='\0';i++,len2++);
if (len2>len1)
{
printf("\n%s is greater than %s",t,s);
}
else if (len1>len2)
{
printf("\n%s is greater than %s",s,t);
}
else
{
printf("\n%s and %s are of the same length",s,t);
}
}
void rev(char s[100])
{
char t[100];
 int j;
for (i=0;s[i]!='\0';i++);
int temp=i;
i--;
for (j=0;i!=-1;i--,j++)
{
t[j]=s[i];
}
t[temp+1]='\0';
printf("Reversed string is: %s",t);
}
int main()
{
int c=1,p;
char s[100],t[100];
printf("\nEnter string 1: ");
scanf("%s",&s);
while(c==1)
{
printf("\nString program");
printf("\n1: Concatenate String");
printf("\n2: Reverse string");
printf("\n3: Comparison");
printf("\n4: Display string");
printf("\n5: Exit program");
printf("\nEnter choice: ");
scanf("%d",&p);
switch(p)
{
case 1:
printf("\nEnter string 2: ");
scanf("%s",&t);
concat(s,t);
 break;
case 2:
rev(s);
break;
case 3:
printf("\nEnter string 2: ");
scanf("%s",&t);
cmp(s,t);
break;
case 4:
for (i=0;s[i]!='\0';i++)
{
printf("%c",s[i]);
}
break;
case 5:
c=2;
break;
default:
printf("\nBad input");
break;
}
}
}

Character arrays are much more efficient compared to string style strings. The
character arrays allow direct access to individual characters and modify them from the
array. By using character arrays, you can also optimize the program by managing the
memory allocation for these data structures.
c) Differentiate between linear arrays and multidimensional arrays. Discuss their
memory representation with a diagram.
Linear Arrays Multidimensional arrays
One dimensional collection of elements Has more than one dimension
 Contiguous memory allocation Contiguous memory allocation of row by
row (row-major) and column by column
(column-major)
Individual elements are accessed using Individual elements are accessed using
single index multiple indices
Can be represented as a simple line of Can be represented as a plane [2 D]or a
elements cube [3 D]

Memory representation for arrays-

Say, we have a single dimensional array int arr[5]={10,20,30,40,50};
Memory allocation layout would look like :
Address Element
1000 10
1004 20
1008 30
1012 40
1016 50

Multidimensional array
0 1 2 3
0 100 A00 104 A01 108 A02 112 A03
1 116 A10 120 A11 124 A12 128 A13
2 132 A20 136 A21 140 A22 144 A23

Row-Major order memory representation

A00 A01 A02 A03 A10 A11 A12 A13 A20 A21 A22 A23
100 104 108 112 116 120 124 128 132 136 140 144
Column-Major order memory representation
A00 A10 A20 A01 A11 A21 A02 A12 A22 A03 A13 A23
100 116 132 104 120 136 108 124 140 112 128 144

d) Design a system for storing and managing customer records (e.g., name, phone
number, and email) using a two-dimensional array. Include functions for adding,
searching, and deleting records. Discuss the choice of data structure.
#include <stdio.h>
#include <string.h>
char data[50][3][100];
int i;
void addrec()
{
char s[100];
char ph[100];
char e[100];
printf("\nEnter name: ");
scanf("%s",s);
printf("\nEnter phone number: ");
scanf("%s",ph);
printf("\nEnter email: ");
scanf("%s",e);
for (i=0;strlen(data[i][0])!=0 && i<50;i++);
if (i>50)
{
printf("\nArray out of bounds");
return;
}
strcpy(data[i][0],s);
strcpy(data[i][1],ph);
strcpy(data[i][2],e);
}
void disprec()
{
for (i=0;strlen(data[i][0])!=0 && i<50;i++)
{
printf("\nName: %s",data[i][0]);
printf("\nPhone number: %s",data[i][1]);
printf("\nEmail: %s",data[i][2]);
}
}
void searchrec()
{
char s[100];
printf("\nEnter name: ");
 scanf("%s",s);
for (i=0;strlen(data[i][0])!=0;i++)
{
if ((strcmp(s,data[i][0]))==0)
{
printf("\nName: %s",data[i][0]);
printf("\nPhone number: %s",data[i][1]);
printf("\nEmail: %s",data[i][2]);
return;
}
}
printf("\nRecord not found");
}
void deleterec()
{
char s[100];
printf("\nEnter name: ");
scanf("%s",s);
for (i=0;strlen(data[i][0])!=0;i++)
{
if ((strcmp(s,data[i][0]))==0)
{
strcpy(data[i][0],"");
strcpy(data[i][1],"");
strcpy(data[i][2],"");
printf("\nRecord deleted");
return;
}
}
printf("\nRecord not found");
}
int main()
{
int c=1,p;
for (i=0;i<50;i++)
{
data[i][0][0]='\0';
}
while (c==1)
{
printf("\nArray program for customers ");
printf("\n1: Insert record");
printf("\n2: Search record");
printf("\n3: Display records");
printf("\n4: Delete record");
printf("\n5: Exit program");
printf("\nEnter choice: ");
scanf("%d",&p);
switch(p)
{
case 1:
addrec();
break;
case 2:
searchrec();
break;
case 3:
disprec();
break;
case 4:
deleterec();
break;
case 5:
c=2;
break;
default:
 printf("\nBad input");
break;
}
}
}
e) Apply the concept of sparse matrices to represent a chessboard with the
positions of all pieces marked. Write an algorithm to initialize, update, and display
the board state.
Pseudocode-
DEFINE BOARD_SIZE=8
DEFINE MAX_PIECES=32

STRUCT pieces
INTEGER row
INTEGER col
CHARACTER piece

DECLARE board[MAX_PIECES] AS pieces

DECLARE Count AS INTEGER=0

FUNCTION initializeBoard()
ADD piece to board[Count] with row=0, col=0, piece= "WR"
Count++
ADD piece to board[Count] with row=0, col=7, piece= "WR"
Count++
ADD piece to board[Count] with row=0, col=1, piece= "WN"
Count++
ADD piece to board[Count] with row=0, col=6, piece= "WN"
Count++
ADD piece to board[Count] with row=0, col=2, piece= "WB"
Count++
ADD piece to board[Count] with row=0, col=5, piece= "WB"
Count++
ADD piece to board[Count] with row=0, col=3, piece= "WQ"
 Count++
ADD piece to board[Count] with row=0, col=4, piece= "WK"
Count++
FOR col=0 TO 7
ADD piece to board[Count] with row=1, col=col, piece= "WP"
Count++
ADD piece to board[Count] with row=7, col=0, piece= "BR"
Count++
ADD piece to board[Count] with row=7, col=7, piece= "BR"
Count++
ADD piece to board[Count] with row=7,col=1, piece="BN"
Count++
ADD piece to board[Count] with row=7, col=6, piece="BN"
Count++
ADD piece to board[Count] with row=7, col=2, piece="BB"
Count++
ADD piece to board[Count] with row=7, col=5, piece="BB"
Count++
ADD piece to board[Count] with row=7, col=3, piece="BQ"
Count++
ADD piece to board[Count] with row=7, col=4, piece="BK"
Count++
FOR col=0 TO 7
ADD piece to board[Count] with row=6, col=col, piece="BP"
Count++
PRINT "Board initialized"
FUNCTION updatePosition(oldRow, oldCol, newRow, newCol)
FOR each piece in board
IF piece.row==oldRow AND piece.col==oldCol
piece.row=newRow
piece.col=newCol
RETURN
 PRINT "Piece not found at the given position"

FUNCTION displayBoard()
DECLARE chessboard[BOARD_SIZE][BOARD_SIZE] AS CHARACTER initialized to
'_'

FOR each piece in board

chessboard[piece.row][piece.col]=piece.piece

PRINT chessboard

MAIN
DECLARE C=1, P
WHILE C==1
SWITCH(C)
CASE 1
initializeBoard()
displayBoard
CASE 2
displayBoard()
CASE 3
updatePosition()
displayBoard
CASE 4
c=2
DEFAULT
PRINT "Bad input"
f) Analyze a scenario where a hospital stores patient records in a multidimensional array.
Write an algorithm to retrieve all patients admitted on a specific date and discuss the
efficiency of using arrays for this purpose.
Pseudocode-
DECLARE patients[MAX][3][100] AS STRING
DECLARE REQDATE AS STRING
DECLARE result[MAX][3][100] AS STRING
DECLARE count AS INTEGER

FUNCTION filterbyadm(REQDATE)
count=0
FOR i=0 TO i=MAX
IF (patients[i][2]==REQDATE)
result[count][0]=patients[i][0]
result[count][1]=patients[i][1]
result[count][2]=patients[i][2]
count++
IF count==0
PRINT "No patients admitted on this date"
RETURN
PRINT count + "patients registered on this day :-"
FOR i=0 TO count-1
PRINT "Name: "+result[i][0]
PRINT "ID: "+result[i][1]
PRINT "AdmDate: "+result[i][2]

Efficiency-
Time complexity : The time complexity of the function is O(n), We loop through all the
patients once.
Space complexity: The space complexity of the function is O(n) because we store up to
n patients in the result array.
This algorithm is efficient for small to medium sized datasets but large datasets have
better alternatives.
_________________________________________________________________________________
2)
a) Design an algorithm to insert and delete elements in a circular queue
represented using an array.
Pseudocode-
DECLARE SIZE=5
int a[SIZE],front=-1,rear=-1
FUNCTION insert(int n)
IF (rear+1)%SIZE==front
 PRINT "Queue is full"
RETURN
IF front==-1
front++
rear=(rear+1)%SIZE
a[rear]=n
PRINT "Inserted "+n
FUNCTION delete()
{
IF (front==-1)
PRINT "Queue is empty"
RETURN
PRINT "Deleted "+a[front]
IF (front==rear)
front=-1
rear=-1
ELSE
front=(front+1)%SIZE
}
FUNCTION display()
{
IF front==-1
PRINT "Queue is empty"
RETURN
PRINT "Queue elements"
i=front
WHILE TRUE
PRINT a[i]
IF i==rear
BREAK
i=(i+1)%SIZE
}
b) Propose a solution for managing browser history using a stack. Implement
operations to navigate back and forward in the history. Critique the limitations of
this approach and suggest improvements.
DECLARE char forward[50], back[50], current=NULL
FUNCTION newpage(char page[50])
push(back,page)
forward=NULL
current=page
FUNCTION goback()
IF back-> EMPTY
PRINT "No pages to go back to"
ELSE
push(forward,current)
current=pop(back)
FUNCTION goforward()
IF forward-> EMPTY
PRINT "No pages to go forward to"
ELSE
push(back,current)
current=pop(forward)
FUNCTION display()
PRINT current
Critique
Memory usage- Both stacks grow in size as pages are visited and will lead to excessive
memory usage.
Navigation- This only supports linear navigation and you can’t visit a random page in
this structure.
Improvements-
• Include usage of doubly linked list which can replace stacks to allow efficient
jumping between histories.
• Include metadata and timestamps
• Introduce bookmarking to access frequently visited pages.
c) Explain and implement the process of converting infix expressions to both
postfix and prefix notations. Discuss the role of stacks in these conversions.
Infix to prefix
FUNCTION inftopref(char expression[100])
DECLARE string reverse
FOR i=LENGTH(expression)-1 TO 0
IF expression[i]=='('
APPEND ')' TO reverse
ELSE IF expression[i]==')'
APPEND ')' TO reverse
ELSE
APPEND expression[i] TO reverse
DECLARE char foperators[50];
DECLARE string result;
FOR EACH character c IN reverse
IF c IS an operand
APPEND c TO result
ELSE IF c=='('
push(operators,c)
ELSE IF c==')'
WHILE TOP(operators)!='('
APPEND TOP(operators) TO result
pop(operators)
ELSE IF c IS an operator
WHILE (operators -> NOT EMPTY) &
(precedence(c)<=precedence(TOP(operators)))
APPEND pop(operators)->result
PUSH c TO operators
WHILE operators-> NOT EMPTY
APPEND pop(operators)->result
REVERSE result
RETURN result
FUNCTION precedence(operator)
IF operator=='+' OR operator=='-'
RETURN 1
ELSE IF operator=='*' OR operator=='/'
RETURN 2
 ELSE IF operator=='^'
RETURN 3
RETURN 0
Infix to postfix
FUNCTION inftopost(char expression[100])
DECLARE char operators[50]
DECLARE string result
FOR EACH character c IN expression
IF c IS an operand
APPEND c TO result
ELSE IF c=='('
PUSH (operators,c);
ELSE IF c=')'
WHILE TOP(operators)!='('
APPEND pop(operators) TO result
POP operators
ELSE IF c IS an operator
WHILE operators->NOT EMPTY &
precedence(c)>=precedence(TOP(operators))
APPEND pop(operators) TO result
PUSH c TO operators
WHILE operators->NOT EMPTY
APPEND pop(operators) TO result
RETURN result

FUNCTION precedence(char operator)

IF operator=='+' OR operator=='-'
RETURN 1
ELSE IF operator=='*' OR operator=='/'
RETURN 2
ELSE IF operator=='^'
RETURN 3
RETURN 0
 Role of stacks in this conversion
• Maintaining order- Stacks ensure that the operators and operands are stored one
by one in the correct order
• Handling Parentheses- They also handle the parentheses to ensure expressions
are grouped correctly
• Push- The operators are pushed onto the stack when are encountered in the
expression
• Pop- The operators are popped from the stack and added to the output when
their precedence is lower or equal to the upcoming operator
d) Implement the Tower of Hanoi problem using recursion for 4 disks and trace the
output step by step.
#include <stdio.h>
#include <string.h>
void moveup(char c[3])
{
char temp;
temp=c[1];
c[1]=c[2];
c[2]=temp;
}
void movedown(char c[3])
{
char temp;
temp=c[0];
c[0]=c[1];
c[1]=temp;
}
void solve(char c[3],int n)
{
if (n==1)
{
printf("\nMove disk from %c to %c",c[0],c[2]);
}
else
{
 char t[3];
strcpy(t,c);
moveup(c);
solve(c,n-1);
strcpy(c,t);
solve(c,1);
strcpy(c,t);
movedown(c);
solve(c,n-1);
}
}
int main()
{
int n;
char c[3]={'A','B','C'};
printf("\nEnter number of discs: ");
scanf("%d",&n);
solve(c,n);
}
e) Develop a parenthesis matching algorithm using a stack to check the validity of
mathematical expressions. For example, evaluate whether expressions like
((A+B)*(C-D)) are correctly parenthesized.
Pseudocode-
DECLARE s[50]
FUNCTION validpar(char expression[100])
FOR EACH character IN expression
IF character=='('
push(s,character)
ELSE IF character==')'
IF s-> EMPTY
RETURN false
ELSE
pop(s)
IF s-> NOT EMPTY
RETURN false
RETURN true
The given algorithm checks for each and every character in the expression, when a ‘(’ is
encountered, it appends it into the stack and after another ‘)’ is encountered, it matches
this parentheses with the ‘(’ and pops it from the stack.

3)
a) Construct a singly linked list to store integers. Write a function to search for a
given element and return its position.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct node
{
int data;
 struct node* link;
};
struct node *first=NULL,*next=NULL,*cur=NULL,*temp=NULL;
void createnode()
{
first=(struct node*)malloc(sizeof(struct node));
temp=(struct node*)malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d",&temp->data);
first->link=temp;
printf("\nNode added");
}
void appendnode()
{
cur=(struct node*)malloc(sizeof(struct node));
temp=(struct node*)malloc(sizeof(struct node));
temp=first;
temp=temp->link;
while(temp->link!=NULL)
{
temp=temp->link;
}
printf("\nEnter data: ");
scanf("%d",&cur->data);
temp->link=cur;
printf("\nNode appended");
}
void insertnode()
{
int pos;
int c=1;
printf("\nEnter position: ");
scanf("%d",&pos);
 temp=(struct node*)malloc(sizeof(struct node));
cur=(struct node*)malloc(sizeof(struct node));
temp=first;
while((temp!=NULL) && (c<=pos))
{
if(c==pos)
{
printf("\nData: ");
scanf("%d",&cur->data);
cur->link=temp->link;
temp->link=cur;
break;
}
temp=temp->link;
c++;
}
if (c!=pos)
{
printf("\nInvalid position");
}
}
void display()
{
temp=(struct node*)malloc(sizeof(struct node));
temp=first;
temp=temp->link;
if (temp==NULL)
{
printf("\nEmpty linked list");
}
else
{
printf("%d",temp->data);
 temp=temp->link;
while(temp!=NULL)
{
printf("->%d",temp->data);
temp=temp->link;
}
}
}
void searchnode()
{
int pos=0,t=0,s;
cur=(struct node*)malloc(sizeof(struct node));
temp=(struct node*)malloc(sizeof(struct node));
temp=first;
printf("\nEnter data to search: ");
scanf("%d",&s);
temp=temp->link;
while (temp!=NULL)
{
pos++;
if (temp->data==s)
{
printf("\nInteger found at position: %d",pos);
t=1;
break;
}
temp=temp->link;
}
if (t==0)
{
printf("\nInteger not found in linked list");
}
}
void del()
{
int s,t=0;
temp=(struct node*)malloc(sizeof(struct node));
cur=(struct node*)malloc(sizeof(struct node));
temp=first;
printf("\nEnter data to delete:");
scanf("%d",&s);
while(temp->link!=NULL)
{
cur=temp->link;
if (cur->data==s)
{
temp->link=cur->link;
printf("\nElement deleted");
t=1;
}
temp=temp->link;
}
if (t==0)
{
printf("\nInteger not found");
}
}
int main()
{
int c=1;
int p;
while (c==1)
{
printf("\nSingley linked list for integers");
printf("\n1: Create node");
printf("\n2: Insert node");
printf("\n3: Append node");
printf("\n4: Delete node");
printf("\n5: Display node");
printf("\n6: Search node");
printf("\n7: Exit the program");
printf("\nEnter the choice: ");
scanf("%d",&p);
switch(p)
{
case 1:
createnode();
break;
case 2:
insertnode();
break;
case 3:
appendnode();
break;
case 4:
del();
break;
case 5:
display();
break;
case 6:
searchnode();
break;
case 7:
c=2;
break;
default:
printf("\nBad input");
 }
}
clrscr();
return 0;
}
b) Construct a singly linked list-based program to store and manage student
records (e.g., roll number, name, and marks). Include operations for insertion,
deletion, and searching.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct node
{
int rno;
char name[100];
int marks;
struct node* link;
};
struct node *first=NULL,*next=NULL,*cur=NULL,*temp=NULL;
void createnode()
{
first=(struct node*)malloc(sizeof(struct node));
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter roll no: ");
scanf("%d",&temp->rno);
printf("\nEnter name: ");
scanf("%s",&temp->name);
printf("\nEnter marks: ");
scanf("%d",&temp->marks);
first->link=temp;
}
void display()
{
temp=(struct node*)malloc(sizeof(struct node));
 temp=first;
temp=temp->link;
if(temp==NULL)
{
printf("\nEmpty linked list");
}
else
{
printf("\n1 \nRoll No: %d",temp->rno);
printf("\nName: %s",temp->name);
printf("\nMarks: %d",temp->marks);
printf("\n__________________\n");
temp=temp->link;
while(temp!=NULL)
{
printf("\n->\nRoll No: %d",temp->rno);
printf("\nName: %s",temp->name);
printf("\nMarks: %d",temp->marks);
temp=temp->link;
}
}
}
void insertnode()
{
int pos=0,s,t=0;
temp=(struct node*)malloc(sizeof(struct node));
cur=(struct node*)malloc(sizeof(struct node));
temp=first;
printf("\nEnter position: ");
scanf("%d",&s);
while(temp!=NULL && pos<=s )
{
pos++;
 if (pos==s)
{
printf("\nEnter roll no: ");
scanf("%d",&cur->rno);
printf("\nEnter name: ");
scanf("%s",&cur->name);
printf("\nEnter marks: ");
scanf("%d",&cur->marks);
cur->link=temp->link;
temp->link=cur;
t=1;
break;
}
temp=temp->link;
}
if (t==0)
{
printf("\nInvalid position");
}
}
void del()
{
int n,t=0;
temp=(struct node*)malloc(sizeof(struct node));
cur=(struct node*)malloc(sizeof(struct node));
temp=first;
printf("\nEnter roll no: ");
scanf("%d",&n);
if (temp==NULL)
{
printf("\nEmpty linked list");
return;
}
 while(temp->link!=NULL)
{
cur=temp->link;
if (cur->rno==n)
{
printf("\nRecord deleted");
temp->link=cur->link;
t=1;
break;
}
temp=temp->link;
}
if(t==0)
{
printf("\nRecord not found");
}
}
void searchnode()
{
int s,t=0;
temp=(struct node*)malloc(sizeof(struct node));
temp=first;
printf("\nEnter roll no: ");
scanf("%d",&s);
temp=temp->link;
while(temp!=NULL)
{
if (temp->rno==s)
{
printf("\nRoll No: %d",temp->rno);
printf("\nName: %s",temp->name);
printf("\nMarks: %d",temp->marks);
t=1;
 break;
}
temp=temp->link;
}
if (t==0)
{
printf("\nRoll no not found");
}
}
int main()
{
int c=1,p;
while (c==1)
{
printf("\nSingley linked list for students");
printf("\n1: Create list");
printf("\n2: Insert record");
printf("\n3: Delete record");
printf("\n4: Search record");
printf("\n5: Display record");
printf("\n6: Exit the program");
printf("\nEnter the choice: ");
scanf("%d",&p);
switch(p)
{
case 1:
createnode();
break;
case 2:
insertnode();
break;
case 3:
del();
 break;
case 4:
searchnode();
break;
case 5:
display();
break;
case 6:
c=2;
break;
default:
printf("\nBad input");
break;
}
}
return 0;
}
c) Create a task management system using a singly linked list, where each node stores
task details (ID, description, priority). Implement functions to add, delete, and search
tasks based on priority.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
int id;
char description[100];
char priority[50];
struct node*link;
};
struct node *first=NULL,*temp,*cur;
int pval(char a[50])
{
if(strcmp(a,"high")==0)
 {
return 3;
}
else if(strcmp(a,"medium")==0)
{
return 2;
}
else if(strcmp(a,"low")==0)
{
return 1;
}
return 0;
}
void createnode()
{
first=(struct node*)malloc(sizeof(struct node));
temp=first;
printf("\nEnter ID:");
scanf("%d",&temp->id);
printf("\nEnter description:");
getchar();
fgets(temp->description,sizeof(temp->description),stdin);
printf("\nEnter priority:");
fgets(temp->priority,sizeof(temp->priority),stdin);
temp->link=NULL;
}
void display()
{
temp=first;
if(temp==NULL)
{
printf("\nEmpty priority list");
return;
 }
while(temp!=NULL)
{
printf("\nID:%d",temp->id);
printf("\nDescription:%s",temp->description);
printf("\nPriority:%s",temp->priority);
temp=temp->link;
}
}
void insertnode()
{
cur=(struct node*)malloc(sizeof(struct node));
printf("\nEnter id:");
scanf("%d",&cur->id);
getchar();
printf("\nEnter description:");
fgets(cur->description,sizeof(cur->description),stdin);
printf("\nEnter priority:");
fgets(cur->priority,sizeof(cur->priority),stdin);
cur->link=NULL;
if(first==NULL)
{
first=cur;
}
else
{
temp=first;
if(pval(cur->priority)>=pval(first->priority))
{
cur->link=first;
first=cur;
}
else
 {
while(temp->link!=NULL&&pval(cur->priority)<pval(temp->link-
>priority))
{
temp=temp->link;
}
cur->link=temp->link;
temp->link=cur;
}
}
}
void del()
{
int id;
printf("\nEnter ID of the task to delete:");
scanf("%d",&id);

temp=first;
if(temp==NULL)
{
printf("\nEmpty priority list\n");
return;
}

if(temp->id==id)
{
first=temp->link;
return;
}

while(temp->link!=NULL&&temp->link->id!=id)
{
temp=temp->link;
}
 if(temp->link==NULL)
{
printf("\nTask not found\n");
return;
}

temp->link=temp->link->link;
}

void searchtask()
{
char priority[50];
printf("\nEnter priority to search (high/medium/low):");
getchar();
fgets(priority,sizeof(priority),stdin);

temp=first;
int found=0;
while(temp!=NULL)
{
if(strcmp(temp->priority,priority)==0)
{
printf("\nID:%d",temp->id);
printf("\nDescription:%s",temp->description);
printf("\nPriority:%s",temp->priority);
found=1;
}
temp=temp->link;
}

if(!found)
{
 printf("\nNo tasks found with %s priority.\n",priority);
}
}

int main()
{
int c=1,p;
while(c==1)
{
printf("\nPriority list using linked list");
printf("\n1:Create priority list");
printf("\n2:Insert tasks");
printf("\n3:Delete task");
printf("\n4:Search tasks");
printf("\n5:Display tasks");
printf("\n6:Exit program");
printf("\nEnter choice:");
scanf("%d",&p);
switch(p)
{
case 1:
createnode();
break;
case 2:
insertnode();
break;
case 3:
del();
break;
case 4:
searchtask();
break;
case 5:
 display();
break;
case 6:
c=2;
break;
default:
printf("\nBad input\n");
break;
}
}
return 0;
}

d) Design a doubly linked list and implement operations to insert and delete a node
at a given position.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* prev;
struct node* next;
};
struct node *prev=NULL,*temp=NULL,*next=NULL,*first=NULL,*cur=NULL;
void createnode()
{
first=(struct node*)malloc(sizeof(struct node));
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter data: ");
scanf("%d",&temp->data);
temp->prev=first;
first->next=temp;
}
void insertnode()
{
 int c,pos=1;
temp=(struct node*)malloc(sizeof(struct node));
cur=(struct node*)malloc(sizeof(struct node));
temp=first;
printf("\nEnter position: ");
scanf("%d",&c);
while (temp!=NULL && pos<c)
{
temp=temp->next;
pos++;
}
if (pos!=c)
{
printf("\nInvalid position");
return;
}
printf("\nEnter data: ");
scanf("%d",&cur->data);
cur->prev=temp;
cur->next=temp->next;
temp->next=cur;
}
void del()
{
int c,pos=1;
temp=(struct node*)malloc(sizeof(struct node));
temp=first;
if (temp==NULL)
{
printf("\nEmpty doubly linked list");
return;
}
printf("\nEnter position: ");
 scanf("%d",&c);
while (temp!=NULL && pos<c)
{
pos++;
temp=temp->next;
}
if (pos!=c)
{
printf("\nInvalid position");
return;
}
cur=temp->next;
cur=cur->next;
temp->next=cur;
}
void display()
{
temp=(struct node*)malloc(sizeof(struct node));
temp=first;
if (temp==NULL)
{
printf("\nEmpty doubly linked list");
return;
}
temp=temp->next;
printf("\n%d",temp->data);
temp=temp->next;
while(temp!=NULL)
{
printf("->%d",temp->data);
temp=temp->next;
}
}
int main()
{
int p,c=1;
while (c==1)
{
printf("\nDoubly linked list");
printf("\n1: Create node");
printf("\n2: Insert node");
printf("\n3: Delete node");
printf("\n4: Display node");
printf("\n5: Exit program");
printf("\nEnter choice: ");
scanf("%d",&p);
switch(p)
{
case 1:
createnode();
break;
case 2:
insertnode();
break;
case 3:
del();
break;
case 4:
display();
break;
case 5:
c=2;
break;
default:
printf("\nBad input");
}
 }
return 0;
}
e) Assess the suitability of a singly linked list for representing train routes between
stations. Implement operations for adding a new station and deleting an existing
station. Compare its performance with an array-based implementation.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
char station[50];
int distance;
struct node* link;
};
struct node *first=NULL,*cur=NULL,*temp=NULL;
void add()
{
cur=(struct node*)malloc(sizeof(struct node));
printf("\nEnter station name: ");
scanf("%s",cur->station);
printf("Enter distance to the next station: ");
scanf("%d",&cur->distance);
cur->link=NULL;
if(first==NULL)
{
first=cur;
printf("\nRoute starting station added.");
}
else
{
temp=first;
while(temp->link!=NULL)
{
 temp=temp->link;
}
temp->link=cur;
printf("\nStation added to the route.");
}
}
void del()
{
char sname[50];
int found=0;
if(first==NULL)
{
printf("\nThe route is empty, no station to delete.");
return;
}
printf("\nEnter station name to delete: ");
scanf("%s",sname);
temp=first;
struct node* prev=NULL;
while(temp!=NULL)
{
if(strcmp(temp->station,sname)==0)
{
found=1;
if(prev==NULL)
{
first=temp->link;
}
else
{
prev->link=temp->link;
}
printf("\nStation '%s' deleted.",sname);
 break;
}
prev=temp;
temp=temp->link;
}
if(found==0)
{
printf("\nStation '%s' not found in the route.",sname);
}
}
void display()
{
if(first==NULL)
{
printf("\nThe route is empty.");
}
else
{
temp=first;
printf("\nTrain Route:\n");
while(temp!=NULL)
{
printf("%s (%d km)",temp->station,temp->distance);
temp=temp->link;
if(temp!=NULL)
{
printf(" -> ");
}
}
printf("\n");
}
}
int main()
{
int c=1,p;
printf("\nTrain Route System");
while(c==1)
{
printf("\n1: Add station");
printf("\n2: Delete station");
printf("\n3: Display route");
printf("\n4: Exit");
printf("\nEnter choice: ");
scanf("%d",&p);
switch(p)
{
case 1:
add();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
c=0;
break;
default:
printf("\nBad input.");
}
}
return 0;
}
Performance comparison

Operation Array - based Linked- list Based

Adding stations O(1) O(n)
 Deleting stations O(n) O(n)
Display route O(n) O(n)
Memory overhead Dynamic, extra for
Fixed size
pointers

4)
a) Construct a binary search tree from the elements {15, 10, 20, 8, 12, 17, 25} and
perform in-order, pre-order, and post-order traversals.
Elements={15,10,20,8,12,17,25}
Constructing binary tree-
Step 1-

Step 2-
Step 3-

Step 4-

Step 5-
Step 6-

in-order
LNR[Left-Node-Right]: {8,10,12,15,17,20,25}
pre-order
NLR[Node-Left-Right]: {15,10,8,12,20,17,25}
post-order
LRN[Left-Right-Node]: {8,12,10,17,25,20,15}
b) Differentiate between AVL trees and Binary Search Trees. Explain the
significance of balancing in AVL trees with an example
Binary Search Tree AVL Tree
• It is not a balanced tree. • It is a balanced tree.
• Nodes do not have to follow • Nodes haves to follow balance
balance factor. factor (i.e. difference between
depth of left and right subtree
should be either 0,1 or -1).
• The depth of tree is O(n). • The depth of tree is O(logn).
• Insertions and deletions are easy • Insertions and deletions require
because no rotations are required. rotations.
• Inefficient searching since there • Searching is efficient and faster
are large number of nodes due to balancing of depth.
• Simple to implement • Complex to implement

Note:- Every AVL tree is a binary search tree but not every binary search tree is an AVL
tree.
Significance
As mentioned before, AVL trees differ from binary search trees because of their balance
factor at every node and this is a key reason to which they are used. The balance factor
ensures that the that tree is a balanced tree and this ensures faster searching as we will
see in the example below.

Consider this example for the binary search tree, Now to access element 1, we will have
to go through 4 levels. Now let’s see the same example through an AVL three which is a
balanced binary search tree.

In this, we only have to go through two levels to access the element 1. This shows the
efficiency in traversing elements through the AVL tree when compared to a binary
search tree.

c) Explain and implement the insertion and rotation process in AVL trees to
maintain balance. Provide a step-by-step example for inserting {10, 20, 30, 15, 25}.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
int height;
};
struct node *root=NULL,*left=NULL,*right=NULL,*temp=NULL;
int height(struct node *n)
{
if(n==NULL)
{
return 0;
}
else
{
return n->height;
}
}
int getbal(struct node *n)
{
if(n==NULL)
{
return 0;
}
else
{
return height(n->left)-height(n->right);
}
}
struct node *rr(struct node *y)
{
 struct node *x=y->left;
struct node *T2=x->right;
x->right=y;
y->left=T2;
if(height(y->left)>height(y->right))
{
y->height=height(y->left)+1;
}
else
{
y->height=height(y->right)+1;
}
if(height(x->left)>height(x->right))
{
x->height=height(x->left)+1;
}
else
{
x->height=height(x->right)+1;
}
return x;
}
struct node *lr(struct node *x)
{
struct node *y=x->right;
struct node *T2=y->left;
y->left=x;
x->right=T2;
if(height(x->left)>height(x->right))
{
x->height=height(x->left)+1;
}
else
 {
x->height=height(x->right)+1;
}
if(height(y->left)>height(y->right))
{
y->height=height(y->left)+1;
}
else
{
y->height=height(y->right)+1;
}
return y;
}
struct node *insert(struct node *node,int data)
{
if(node==NULL)
{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->data=data;
temp->left=NULL;
temp->right=NULL;
temp->height=1;
return temp;
}
if(data<node->data)
{
node->left=insert(node->left,data);
}
else if(data>node->data)
{
node->right=insert(node->right,data);
}
else
 {
return node;
}
if(height(node->left)>height(node->right))
{
node->height=height(node->left)+1;
}
else
{
node->height=height(node->right)+1;
}
int bal=getbal(node);
if(bal>1&&data<node->left->data)
{
return rr(node);
}
if(bal<-1&&data>node->right->data)
{
return lr(node);
}
if(bal>1&&data>node->left->data)
{
node->left=lr(node->left);
return rr(node);
}
if(bal<-1&&data<node->right->data)
{
node->right=rr(node->right);
return lr(node);
}
return node;
}
void createnode()
{
int data;
printf("\nEnter data: ");
scanf("%d",&data);
root=insert(root,data);
}
void insertnode()
{
int data;
if(root==NULL)
{
printf("\nTree is empty. Create root first.");
return;
}
printf("\nEnter data: ");
scanf("%d",&data);
root=insert(root,data);
}
void display(struct node *node,int level)
{
if(node!=NULL)
{
display(node->right,level+1);
int i;
for(i=0;i<level;i++)
{
printf(" ");
}
printf("%d\n",node->data);
display(node->left,level+1);
}
}
int main()
{
int p,c=1;
while(c==1)
{
printf("\nAVL Tree");
printf("\n1: Create root");
printf("\n2: Insert node");
printf("\n3: Display nodes");
printf("\n4: Exit program");
printf("\nEnter choice: ");
scanf("%d",&p);
switch(p)
{
case 1:
createnode();
break;
case 2:
insertnode();
break;
case 3:
if(root==NULL)
{
printf("\nTree is empty.");
}
else
{
printf("\nTree structure:\n");
display(root,0);
}
break;
case 4:
c=2;
break;
 default:
printf("\nBad input");
}
}
}
AVL tree for {10,20,30,15,25}

Step 1

Step 2

Balance Factor= 2

Balance Factor= 1

Balance Factor= 0

Single rotation is performed on the tree since imbalance(balance factor is not -1,0 or 1)
is seen at level 1.

Step 3
There is no imbalance at any node.

d) Construct an AVL tree for a financial application that tracks stock prices.
Demonstrate how balance is maintained during insertion and deletion operations,
and critique its applicability to high-frequency trading systems.
#include <stdio.h>
#include <stdlib.h>
struct node
{
float price;
struct node *left;
struct node *right;
int height;
};
struct node *root=NULL,*temp=NULL;
int height(struct node *n)
{
if(n==NULL)
 {
return 0;
}
else
{
return n->height;
}
}
int getbal(struct node *n)
{
if(n==NULL)
{
return 0;
}
else
{
return height(n->left)-height(n->right);
}
}
struct node *rr(struct node *y)
{
struct node *x=y->left;
struct node *T2=x->right;
x->right=y;
y->left=T2;
if(height(y->left)>height(y->right))
{
y->height=height(y->left)+1;
}
else
{
y->height=height(y->right)+1;
}
 if(height(x->left)>height(x->right))
{
x->height=height(x->left)+1;
}
else
{
x->height=height(x->right)+1;
}
return x;
}

struct node *lr(struct node *x)

{
struct node *y=x->right;
struct node *T2=y->left;
y->left=x;
x->right=T2;
if(height(x->left)>height(x->right))
{
x->height=height(x->left)+1;
}
else
{
x->height=height(x->right)+1;
}
if(height(y->left)>height(y->right))
{
y->height=height(y->left)+1;
}
else
{
y->height=height(y->right)+1;
}
 return y;
}
struct node *insert(struct node *node,float price)
{
if(node==NULL)
{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->price=price;
temp->left=NULL;
temp->right=NULL;
temp->height=1;
return temp;
}
if(price<node->price)
{
node->left=insert(node->left,price);
}
else if(price>node->price)
{
node->right=insert(node->right,price);
}
else
{
return node;
}
if(height(node->left)>height(node->right))
{
node->height=height(node->left)+1;
}
else
{
node->height=height(node->right)+1;
}
 int bal=getbal(node);
if(bal>1&&price<node->left->price)
{
return rr(node);
}
if(bal<-1&&price>node->right->price)
{
return lr(node);
}
if(bal>1&&price>node->left->price)
{
node->left=lr(node->left);
return rr(node);
}
if(bal<-1&&price<node->right->price)
{
node->right=rr(node->right);
return lr(node);
}
return node;
}
struct node *min(struct node *node)
{
struct node *cur=node;
while(cur&&cur->left!=NULL)
{
cur=cur->left;
}
return cur;
}
struct node *del(struct node *root,float price)
{
if(root==NULL)
{
return root;
}
if(price<root->price)
{
root->left=del(root->left,price);
}
else if(price>root->price)
{
root->right=del(root->right,price);
}
else
{
if(root->left==NULL||root->right==NULL)
{
struct node *temp=root->left?root->left:root->right;
if(temp==NULL)
{
temp=root;
root=NULL;
}
else
{
*root=*temp;
}
}
else
{
struct node *temp=min(root->right);
root->price=temp->price;
root->right=del(root->right,temp->price);
}
}
 if(root==NULL)
{
return root;
}

root->height=1+((height(root->left)>height(root->right))?height(root-
>left):height(root->right));

int bal=getbal(root);
if(bal>1&&getbal(root->left)>=0)
{
return rr(root);
}
if(bal<-1&&getbal(root->right)<=0)
{
return lr(root);
}
if(bal>1&&getbal(root->left)<0)
{
root->left=lr(root->left);
return rr(root);
}
if(bal<-1&&getbal(root->right)>0)
{
root->right=rr(root->right);
return lr(root);
}

return root;
}
void createnode()
{
float price;
 printf("\nEnter stock price: ");
scanf("%f",&price);
root=insert(root,price);
}
void insertnode()
{
float price;
if(root==NULL)
{
printf("\nTree is empty. Create root first.");
return;
}
printf("\nEnter stock price: ");
scanf("%f",&price);
root=insert(root,price);
}
void delf()
{
float price;
if(root==NULL)
{
printf("\nTree is empty.");
return;
}
printf("\nEnter stock price to delete: ");
scanf("%f",&price);
root=del(root, price);
}
void display(struct node *node,int level)
{
if(node!=NULL)
{
display(node->right,level+1);
 int i;
for(i=0;i<level;i++)
{
printf(" ");
}
printf("%f\n",node->price);
display(node->left,level+1);
}
}
int main()
{
int p,c=1;
while(c==1)
{
printf("\nAVL Tree for Stock Prices");
printf("\n1: Create root");
printf("\n2: Insert stock price");
printf("\n3: Delete stock price");
printf("\n4: Display stock prices");
printf("\n5: Exit program");
printf("\nEnter choice: ");
scanf("%d",&p);
switch(p)
{
case 1:
createnode();
break;
case 2:
insertnode();
break;
case 3:
delf();
break;
 case 4:
if(root==NULL)
{
printf("\nTree is empty.");
}
else
{
printf("\nStock prices tree structure:\n");
display(root,0);
}
break;
case 5:
c=2;
break;
default:
printf("\nBad input");
}
}
}
During the insertion and deletion operations, there are four possible imbalances:-

1. LL imbalance: Left subtree of the left child is taller, Right rotation is performed on
unbalanced node.
2. RR imbalance: Right subtree of the right child is taller, Left rotation is performed
on unbalanced node.
3. LR imbalance: Right subtree of the left child is taller, Left rotation is performed
on left child, followed by right rotation on unbalanced node.
4. RL imbalance: Left subtree of the right child is taller, Right rotation is performed
on the right child, followed by left rotation on unbalanced node.

Applicability in High- Frequency trading systems-

1. Overhead of balancing –
During balancing at times multiple rotations are performed and this results in
computational overhead (i.e. overuse of resources, CPU time, memory,
processing power, etc.). And during times when low latency is required, overhead
of AVL trees would be a hindrance when there are thousands of updates per
second.
2. Time complexity-
HFT systems often deal with real-streaming data where data flows in at superfast
speeds and balancing operations wont be able to keep up pace with them.
3. Memory considerations-
AVL trees require more memory than simpler data structures like hash tables
and hence alternatives are considered.

5.

a) Demonstrate the working of the quick sort algorithm on the array {45, 23, 53,
21, 17}.

Quicksort algorithm-
WHILE too_small_index>too_big_index

WHILE data[too_big_index]<=data[pivot]

++too_big_index

WHILE data[too_small_index]>data[pivot]

--too_small_index

IF too_big_index<too_small_index

SWAP data[too_big_index] & data[too_small_index]

SWAP data[too_small_index]& data [pivot_index]

tbi tsi
45 is set as the pivot element
45 23 53 21 17 23 is set as toobig element
17 is set as toosmall element
0 1 2 3 4

tbi tsi
Since toobig element was smaller
45 23 53 21 17 than pivot 45, tbi index is
incremented.
0 1 2 3 4

tbi tsi
Since, toosmall element was not
45 23 17 21 53 bigger than pivot 45, no change in
element, and since tbi<tsi, data is
swappped
0 1 2 3 4

tbi tsi Since the new toobig element (21) is

smaller than 45, tbi index is
incremented, now 3 pointing to 21.
45 23 17 21 53

0 1 2 3 4

tbi,tsi Since 21 is also smaller than the

pivot, tbi index is again incremented,
45 23 17 21 53 now pointing to index 4, value 53.

0 1 2 3 4

tsi tbi
Since toosmall element is bigger
than pivot (45), it is decremented to
45 23 17 21 53
3, now pointing to 21.

0 1 2 3 4
Now, finally, tsi is smaller than tbi so,
it exits the loop and pivot is swapped
21 23 17 45 53 with tsi value, leaving two sub-arrays
left and right of 45.

0 1 2 3 4

tbi tsi
Now, 23 is the new toobig element
21 23 17 45 53 and 17 becomes new toosmall
element.

0 1 2 3 4

tbi tsi
Both conditions, toobig(23)<pivot(21)
and toosmall(17)>pivot(21) are
21 17 23 45 53
unsatisfied and tbi<tsi is true after
which, values are swapped.
0 1 2 3 4

tbi tsi Now, new toobig(17)<pivot(21) is true

after which tbi index is incremented.
21 17 23 45 53

0 1 2 3 4
 tbi, tsi The toosmall(23)>pivot(21) is true
after which tsi index is decremented.
21 17 23 45 53

0 1 2 3 4

tsi<tbi condition is now reached

again and so pivot and toosmall
17 21 23 45 53 elements are swapped and we get
our sorted array.
0 1 2 3 4

b) Explain and implement hashing with collision resolution using open

addressing. Include functions for insertion, search, and deletion in your
program.
#include <stdio.h>

#include <stdlib.h>

int empty=-2;

int htab[10];

int hash(int key)

return key%10;

void insert(int key)

int i=hash(key);

while(htab[i]!=empty && htab[i]!=-1)

i=(i+1)%10;

htab[i]=key;

printf("\nElement %d inserted at index %d\n",key,i);

}

int search(int key)

int i=hash(key);

int t=i;

while(htab[i]!=empty)

IF (htab[i]==key)

return i;

else

i=(i+1)%10;

IF(i==t)

break;

return -1;

void del(int key)

int i=search(key);

IF (i==-1)

printf("\nElement not found");

else
 {

int t=htab[i];

htab[i]=empty;

printf("\nDeleted element %d from hash table",t);

void display()

printf("\nHash table");

for(int i=0;i<10;i++)

IF(htab[i]==empty)

printf("\n%d: empty");

else

printf("\n%d: %d",i,htab[i]);

int main()

for (int i=0;i<10;i++)

htab[i]=empty;

int c=1,p,k;

while (c==1)
{

printf("\nHash table");

printf("\n1: Insert");

printf("\n2: Delete");

printf("\n3: Display");

printf("\n4: Search");

printf("\n5: Exit program");

printf("\nEnter choice: ");

scanf("%d",&p);

switch(p)

case 1:

printf("\nEnter key: ");

scanf("%d",&k);

insert(k);

break;

case 2:

printf("\nEnter key: ");

scanf("%d",&k);

del(k);

break;

case 3:

display();

break;

case 4:

printf("\nEnter key: ");

scanf("%d",&k);

search(k);

break;

case 5:

c=2;

break;
 default:

printf("\nBad input");

As seen in the program, there is a collision resolution and for this program especially, it
uses linear probing which includes incrementing value by 1 until an empty slot is found.
i=(i+1)%10; in the insert()

Once it reaches the end say i=10, then new value of I becomes 1 which was the initial
value. This is why linear probing is used, it helps in returning the index to the beginning.

c) Implement a search engine feature where user queries are stored in a hash table.
Include collision resolution using chaining. Demonstrate how queries are added,
searched, and deleted.
#include<stdio.h>

#include<stdlib.h>

#include<string.h>

struct node

char query[100];

struct node*link;

};

struct node*htab[10],*temp=NULL,*prev=NULL;

int hash(char*query)

int sum=0;

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

sum+=query[i];

return sum%10;

}
void insert(char*query)

int i=hash(query);

temp=(struct node*)malloc(sizeof(struct node));

strcpy(temp->query,query);

temp->link=NULL;

if(htab[i]==NULL)

htab[i]=temp;

else

temp->link=htab[i];

htab[i]=temp;

void search(char*query)

int i=hash(query);

temp=htab[i];

while(temp!=NULL)

if(strcmp(temp->query,query)==0)

printf("\nQuery found at index %d",i);

return;

temp=temp->link;

printf("\nQuery not found");

return;
}

void del(char*query)

int i=hash(query);

temp=htab[i];

prev=NULL;

while(temp!=NULL)

if(strcmp(temp->query,query)==0)

if(prev==NULL)

htab[i]=temp->link;

else

prev->link=temp->link;

printf("\nQuery deleted");

return;

prev=temp;

temp=temp->link;

printf("\nQuery not found");

void display()

printf("\nSearch Engine Data:");

for(int i=0;i<10;i++)
 {

temp=htab[i];

printf("\n%d: ",i);

while(temp!=NULL)

printf("%s ",temp->query);

temp=temp->link;

int main()

for(int i=0;i<10;i++)

htab[i]=NULL;

int c=1,p;

char query[100];

while(c==1)

printf("\nSearch Engine Menu");

printf("\n1: Insert Query");

printf("\n2: Delete Query");

printf("\n3: Display All Queries");

printf("\n4: Search Query");

printf("\n5: Exit Program");

printf("\nEnter choice: ");

scanf("%d",&p);

switch(p)

case 1:
 printf("\nEnter query: ");

scanf("%s",query);

insert(query);

break;

case 2:

printf("\nEnter query: ");

scanf("%s",query);

del(query);

break;

case 3:

display();

break;

case 4:

printf("\nEnter query: ");

scanf(" %s",query);

search(query);

break;

case 5:

c=2;

break;

default:

printf("\nBad input");

return 0;

query here is a character array and we cannot perform modulo division directly to get a hash value, so we have to
go for alternative options. Here, a for loop can be used to add all the character to integer values and store it into a
variable sum on which the modulo division can be performed.

int hash(char*query)

int sum=0;

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

sum+=query[i];

return sum%10;

Chaining is handled here by chaining which includes usage of singley linked lists.

For deletion of queries, the function has a temp pointer that points to htab[i] where i is the hash key of the
entered query. Another linked list prev is used to store the previous elements linked to the node with target query.

The search function uses the hash key of the entered query and then traverses through the temp linked list using
temp=temp → link as long as the temp is not NULL.

d) Analyze the advantages and disadvantages of using hash functions for

searching in comparison to binary search.

Binary search Hash functions

Time complexity is O(log n) Time complexity is just O(1), also
affected by collisions
Requires sorting No sorting required
Memory-efficient since no extra Requires a lot of memory, especially to
memory is used minimize hash collisions where
chaining is used
Predictable performance Unpredictable since it depends on the
conditions of hash functions
Limited data types More open-source and we can use
many more datatypes
Useful for large sorted datasets Comparatively much useful for large
unsorted dynamic datasets
Has multiple comparisons between the Direct comparison with corresponding
middle element and the required hash
element leading to a lot of time
consumption.

e) Construct a program in C to implement the merge sort algorithm for an array

of integers and trace its execution with a sample array.

Code-
#include <stdio.h>

void merge(int a[],int low,int mid,int high)

printf("\n--- Merging: low=%d, mid=%d, high=%d ---\n", low, mid, high);

int n1=mid-low+1;

int n2=high-mid;

int L[n1], R[n2];

for (int i=0;i<n1;i++)

L[i]=a[low+i];

for (int j=0;j<n2;j++)

R[j]=a[mid+j+1];

printf("Left Subarray: ");

for (int i=0;i<n1;i++)

printf("%d ",L[i]);

printf("\nRight Subarray: ");

for (int j=0;j<n2;j++)

printf("%d ",R[j]);

printf("\n");

int i=0,j=0,k=low;

while (i<n1 && j<n2)

IF (L[i]<=R[j])

a[k]=L[i];

i++;

else

{
 a[k]=R[j];

j++;

k++;

while (i<n1)

a[k]=L[i];

i++;

k++;

while (j<n2)

a[k]=R[j];

j++;

k++;

printf("Merged Array: ");

for (int i=low;i<=high;i++)

printf("%d ",a[i]);

printf("\n--- End of Merging ---\n");

void mergesort(int a[],int low,int high)

IF (low<high)

printf("\n--- Sorting: low=%d, high=%d ---\n", low, high);

int mid=low+(high-low)/2;

mergesort(a,low,mid);

mergesort(a,mid+1,high);
 merge(a,low,mid,high);

int main()

int n;

printf("Enter number of elements: ");

scanf("%d",&n);

int a[n];

printf("\n");

for (int i=0;i!=n;i++)

printf("Enter element: ");

scanf("%d",&a[i]);

printf("\nEnd of entry\nSorting Array...\n");

mergesort(a,0,n-1);

printf("\nSorted Array: ");

for (int i=0;i!=n;i++)

printf("%d ",a[i]);

printf("\n");

return 0;

Output-
6)

a) Design and implement Depth First Search (DFS) and Breadth First Search
(BFS) algorithms for a graph represented as an adjacency matrix. Use an
example graph to demonstrate both traversals.
BFS algorithm pseudocode
int visited[50]

int q[50]

bfs(graph, n, start)

q[50] ->EMPTY

FOR i=0 TO i=n-1

visited[i]=0

ENQUEUE start->q

visited[start]=1

WHILE Q->NOT EMPTY

DEQUEUE vertex from q

PRINT vertex

FOR i=0 TO n-1

IF graph[vertex][i]==1 & visited[i]==0

ENQUEUE i to q

visited[i]=1

DFS algorithm pseudocode

int visited[50]

dfs(graph, visited, vertex, n)

visited[vertex]=1

PRINT vertex

FOR i=0 TO i=n-1

IF graph[vertex][i]==1 & visited[i]==0

dfs(graph, visited, i, n)

Consider graph with following adjacency matrix:

0 1 2 3 4
0 0 1 1 0 0

1 1 0 0 1 1

2 1 0 0 0 0

3 0 1 0 0 0
 4 0 1 0 0 0

The graph of this matrix can be represented as follows-

BFS Output
Step ->Enqueue start vertex -> 0
1: q=[0]
visited=[1,0,0,0,0]
Step ->Dequeue vertex 0 0
2: q=[]
current vertex=0

q=[1] (1 is adjacent)
visited=[1,1,0,0,0]

q=[1,2] (2 is adjacent)
visited=[1,1,1,0,0]
Step ->Dequeue vertex 1 1
3: q=[2]
current vertex=1

q=[2,3] (3 is adjacent)
visited=[1,1,1,1,0]

q=[2,3,4]
visited=[1,1,1,1,1]
Step ->Dequeue vertex 2 2
4: q=[3,4]
 current vertex=2
Step ->Dequeue vertex 3 3
5: q=[4]
current vertex=3
Step ->Dequeue vertex 4 4
6: q=[]
current vertex=4
Step ->Termination
7:

0->1->2->3->4

DFS Output
Step ->vertex 0 is visited 0
1: visited=[1,0,0,0,0]

Adjacent vertices- 1,2

Step ->vertex 1 is visited 0->1
2: visited=[1,1,0,0,0]

Adjacent vertices- 0,3,4

Step ->vertex 3 is visited 0->1->3
3: visited=[1,1,0,1,0]

Adjacent vertices- 1 (skip)

backtrack to vertex 1
Adjacent vertices- 0,3,4
Step ->vertex 4 is visited 0->1->3->4
4: visited=[1,1,0,1,1]

Adjacent vertices- 1(skip)

Backtrack to vertex 1
Backtrack to vertex 0
Adjacent vertices- 1,2
Step ->vertex 2 is visited 0->1->3->4->2
5: visited=[1,1,1,1,1]

Adjacent vertices- 0 (skip)

Step -> Backtrack to vertex 0
6:
Step ->Termination
7:

0->1->3->4->2
b) Model a city's road network as a graph where intersections are nodes and roads
are edges. Use Dijkstra's algorithm to find the shortest path between two
intersections. Illustrate the process with an example.

4
4
1 2

3
2 1

4 2
1
6

Consider this graph with nodes A,B, C, D, E, F and G and respective roads with
distances. The shortest path is calculated using Dijkstra’s algorithm as shown below-

Vertex A B C D E F G
Status 0 1 1 1 1 1 1
Distance 0 3 6 - - - -
Next * A A A A A A

Vertex A B C D E F G
Status 0 0 1 1 1 1 1
Distance 0 3 5 7 - - -
Next * A B B A A A

Vertex A B C D E F G
Status 0 0 0 1 1 1 1
Distance 0 3 5 6 9 7 -
Next * A B C C C A

Vertex A B C D E F G
Status 0 0 0 0 1 1 1
Distance 0 3 5 6 8 7 10
Next * A B C D C D
 Vertex A B C D E F G
Status 0 0 0 0 1 0 1
Distance 0 3 5 6 8 7 8
Next * A B C D C F

Vertex A B C D E F G
Status 0 0 0 0 0 0 1
Distance 0 3 5 6 8 7 8
Next * A B C D C F

Vertex A B C D E F G
Status 0 0 0 0 0 0 0
Distance 0 3 5 6 8 7 8
Next * A B C D C F

The shortest path between A and G can be computed as follows:

A →G ➔(A→B→C→F→G)=3+2+2+1=8

c) Design a social network graph where individuals are nodes and friendships
are edges. Implement BFS and DFS to find the shortest connection between two
individuals and all friends of a given person.

Consider the following graph with nodes as the individuals and edges as friendships-
BFS Output
Step ->Enqueue start vertex -> 0
1: q=[0]
visited=[1,0,0,0,0]
Step ->Dequeue vertex 0 0
2: q=[]
current vertex=0

q=[1] (1 is adjacent)
visited=[1,1,0,0,0]

q=[1,2] (2 is adjacent)
visited=[1,1,1,0,0]

q=[1,2,4] (4 is adjacent)
visited=[1,1,1,0,1]
Step ->Dequeue vertex 1 1
3: q=[2,4]
current vertex=1

q=[2,4,3] (3 is adjacent)
visited=[1,1,1,1,1]
Step ->Dequeue vertex 2 2
4: q=[3,4]
current vertex=2
Step ->Dequeue vertex 4 4
5: q=[3]
current vertex=4
Step ->Dequeue vertex 3 3
6: q=[]
current vertex=3
Step ->Termination
7:

0->1->2->4->3

DFS Output
Step ->vertex 0 is visited 0
1: visited=[1,0,0,0,0]

Adjacent vertices- 1,2,4

Step ->vertex 1 is visited 0->1
2: visited=[1,1,0,0,0]

Adjacent vertices- 3
 Step ->vertex 3 is visited 0->1->3
3: visited=[1,1,0,1,0]

Adjacent vertices- 2,4

Step ->vertex 2 is visited 0->1->3->2
4: visited=[1,1,1,1,0]

Adjacent vertices- 1,3(skip)

Backtrack to 3

Adjacent vertices- 4
Step ->vertex 4 is visited 0->1->3->2->4
5: visited=[1,1,1,1,1]

Adjacent vertices- 0,3 (skip)

Step -> Backtrack to vertex 3
6:
Step ->Termination
7:

0->1->3->2->4

d) Design a graph-based solution for optimizing delivery routes in a logistics

company. Implement Prim’s and Kruskal’s algorithms to find the minimum
spanning tree, and discuss which algorithm is more suitable for real-time
applications.

Consider the following graph for a logistics company

Applying Kruskal’s algorithm

Step 1

Arranging edges in increasing order of cost

BF-1
BC-2
DF-2
BD-3 (Cycle formation)
CE-3
BE-4 (Cycle formation)
DE-4 (Cycle formation)
AB-5
CD-5 (Cycle formation)
EF-6 (Cycle formation)
AC-7 (Cycle formation)

Step 2

Plot graph

MST cost →1+2+2+3+5=13

Applying Prim’s algorithm

Step 1

Vertex A B C D E F
Status 0 1 1 1 1 1
 Cost - 5 7 - - -
Next * A A A A A

Step 2

Vertex A B C D E F
Status 0 0 1 1 1 1
Cost - 5 2 3 4 1
Next * A B B B B

Step 3

Vertex A B C D E F
Status 0 0 1 1 1 0
Cost - 5 2 2 4 1
Next * A B F B B

Step 4

Vertex A B C D E F
Status 0 0 0 1 1 0
Cost - 5 2 2 3 1
Next * A B F C B

Step 5

Vertex A B C D E F
Status 0 0 0 0 1 0
Cost - 5 2 2 3 1
Next * A B F C B

Step 6

Vertex A B C D E F
Status 0 0 0 0 1 0
Cost - 5 2 2 3 1
Next * A B F C B

MST cost = AB+BC+DF+EC+FB=5+2+2+3+1=13

Kruskal’s Prim’s
Edge list graph representation Adjacency matrix representation
Time complexity of O(ElogE) Time complexity of O(E+VlogV)
Sparse graphs Dense graphs
Harder to increment Easier to increment
Sorting all edges is required Sorting is not required
Less suitable for large graphs More suitable