String Matching Algorithms
VerifiedAdded on 2021/03/15
|46
|7009
|239
AI Summary
This assignment involves implementing two string matching algorithms: the Boyer-Moore algorithm using bad character heuristic and the Rabin-Karp algorithm using a rolling hash. The Boyer-Moore algorithm uses a pre-computed bad character table to shift the pattern along the text, while the Rabin-Karp algorithm uses a hash function to quickly verify potential matches. Both algorithms are implemented in C++, with example use cases provided to demonstrate their functionality.
Contribute Materials
Your contribution can guide someone’s learning journey. Share your
documents today.
PARUL UNIVERSITY
FACULTY OF ENGINEERING & TECHNOLOGY
M.Tech. 1st Year
CERTIFICATE
This is to certify that
Ms. Hardika Jadeja with enrolment no. T0920CE024 has successfully completed
his/her laboratory experiments in the Advanced Data Structures (203202102) from the
department of Computer Science Engineering during the academic year 2020-21.
Date of Submission:......................... Staff In charge:...........................
Head Of Department:...........................................
FACULTY OF ENGINEERING & TECHNOLOGY
M.Tech. 1st Year
CERTIFICATE
This is to certify that
Ms. Hardika Jadeja with enrolment no. T0920CE024 has successfully completed
his/her laboratory experiments in the Advanced Data Structures (203202102) from the
department of Computer Science Engineering during the academic year 2020-21.
Date of Submission:......................... Staff In charge:...........................
Head Of Department:...........................................
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
M.TECH- COMPUTER ENGINEERING
M.Tech- CE- 1st SemesterSubject: : 203202102(ADVANCE DATA STRUCTURE)
TABLE OF CONTENT
Sr.
No Experiment Title
Page No
Date of
Performance
Date of
Assessment
Marks(o
ut of 10) Sign
From To
1
List the factors that may influence
the space complexity of a program.
Write a recursive and non-recursive
function to compute n!
1 2
2 Write a program to determine
wheather or not a character string
has an unmatchedparanthesis using
a stack
3 5
3
Write a program in C to
implement insertion and
deletion in AVL trees
6 15
4
Write a program to
implement tree traversal
in tree
16 19
5
Write a program to implement
Divide and Conqure method to
find the maximum andminimum
of N elements
20 22
6
Write a program in C to
implement Breadth First Search 23 24
7
Write a program to
implement DFS (Depth-
First Search).
25 26
8
Write a program in C to create a
minimum Spanning Tree using
Kruskal’s and prime’s algorithm
27 32
9
Write a program to implement
Factorial of N numbers. 33 33
10
Implement the Rabin-Krap
matcher and Boyer Moore
Strings matching algorithms.
34 36
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
M.TECH- COMPUTER ENGINEERING
M.Tech- CE- 1st SemesterSubject: : 203202102(ADVANCE DATA STRUCTURE)
TABLE OF CONTENT
Sr.
No Experiment Title
Page No
Date of
Performance
Date of
Assessment
Marks(o
ut of 10) Sign
From To
1
List the factors that may influence
the space complexity of a program.
Write a recursive and non-recursive
function to compute n!
1 2
2 Write a program to determine
wheather or not a character string
has an unmatchedparanthesis using
a stack
3 5
3
Write a program in C to
implement insertion and
deletion in AVL trees
6 15
4
Write a program to
implement tree traversal
in tree
16 19
5
Write a program to implement
Divide and Conqure method to
find the maximum andminimum
of N elements
20 22
6
Write a program in C to
implement Breadth First Search 23 24
7
Write a program to
implement DFS (Depth-
First Search).
25 26
8
Write a program in C to create a
minimum Spanning Tree using
Kruskal’s and prime’s algorithm
27 32
9
Write a program to implement
Factorial of N numbers. 33 33
10
Implement the Rabin-Krap
matcher and Boyer Moore
Strings matching algorithms.
34 36
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-1
Aim: List the factors that may influence the space complexity of a program. Write a
recursive and non-recursive function to compute n!
Program:
#include<stdio.h>;
#include<conio.h>;
Void main();
{
Int I,r=0,num=1,n,fib;
Printf(“enter the number of limit”);
Scanf(“%d”,&n);
for(i=1;i<=n;i++)
{
Printf(“%d”,r);
fib=r=num;
r=num;
num=fib;
}
Getch();
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-1
Aim: List the factors that may influence the space complexity of a program. Write a
recursive and non-recursive function to compute n!
Program:
#include<stdio.h>;
#include<conio.h>;
Void main();
{
Int I,r=0,num=1,n,fib;
Printf(“enter the number of limit”);
Scanf(“%d”,&n);
for(i=1;i<=n;i++)
{
Printf(“%d”,r);
fib=r=num;
r=num;
num=fib;
}
Getch();
}
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Output:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Output:
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
PRIME NUMBER
#include<stdio.h>
#include<conio.h>
void main()
{
int i,num,j=0,n;
clrscr();
printf("Enter The Number-");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
if(n%i==0)
{
j++;
}
}
if(j==2)
{
printf("Number Is Prime",n);
}
else
{
printf("Number Is Not Prime",n);
}
getch();
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
PRIME NUMBER
#include<stdio.h>
#include<conio.h>
void main()
{
int i,num,j=0,n;
clrscr();
printf("Enter The Number-");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
if(n%i==0)
{
j++;
}
}
if(j==2)
{
printf("Number Is Prime",n);
}
else
{
printf("Number Is Not Prime",n);
}
getch();
}
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Output:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Output:
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
Practical-2
Aim: Write a program to determine wheather or not a character string has an unmatched
paranthesis using a stack.
Program:
#include<stdio.h>
#include<conio.h>
#include<string.h>
int top=-1;
char stack[100];
void push(char);
void pop();
void find_top();
void main()
{
int i;
char a[100];
printf("\nRamizraja \n");
scanf("%s",&a);
for(i=0;a[i]!='\0';i++)
{
if(a[i]=='(')
{
push(a[i]);
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
Practical-2
Aim: Write a program to determine wheather or not a character string has an unmatched
paranthesis using a stack.
Program:
#include<stdio.h>
#include<conio.h>
#include<string.h>
int top=-1;
char stack[100];
void push(char);
void pop();
void find_top();
void main()
{
int i;
char a[100];
printf("\nRamizraja \n");
scanf("%s",&a);
for(i=0;a[i]!='\0';i++)
{
if(a[i]=='(')
{
push(a[i]);
}
Paraphrase This Document
Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
else if(a[i]==')')
{
pop();
}
}
find_top();
}
void push(char a)
{
stack[top]=a;
top++;
}
void pop()
{
if(top==-1)
{
printf("expression is invalid\n");
}
else
{
top--;
}
}
void find_top()
{
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
else if(a[i]==')')
{
pop();
}
}
find_top();
}
void push(char a)
{
stack[top]=a;
top++;
}
void pop()
{
if(top==-1)
{
printf("expression is invalid\n");
}
else
{
top--;
}
}
void find_top()
{
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
if(top==-1)
{
printf("\nexpression is valid\n");
}
else
{
printf("\nexpression is invalid");
}
getch();
}
Output:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
if(top==-1)
{
printf("\nexpression is valid\n");
}
else
{
printf("\nexpression is invalid");
}
getch();
}
Output:
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-3
Aim:Write a program in C to implement insertion and deletion in AVL trees.
Program:
Insertion:
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b);
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-3
Aim:Write a program in C to implement insertion and deletion in AVL trees.
Program:
Insertion:
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b);
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Struct * newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
return x;
}
struct Node *leftRotate(struct Node *x)
{
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Struct * newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
return x;
}
struct Node *leftRotate(struct Node *x)
{
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
return y;
}
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct Node* insert(struct Node* node, int key)
{
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
return y;
}
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct Node* insert(struct Node* node, int key)
{
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left),
height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left),
height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
Paraphrase This Document
Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
}
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
struct Node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf("Preorder traversal of the constructed insertion in AVL"" tree is \n");
preOrder(root);
return 0;
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
}
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
struct Node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf("Preorder traversal of the constructed insertion in AVL"" tree is \n");
preOrder(root);
return 0;
}
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
OUTPUT:
Deletion:
#include<stdio.h>
#include<stdlib.h>
structNode
{
intkey;
structNode *left;
structNode *right;
intheight;
};
intmax(inta, intb);
intheight(structNode *N)
{
if(N == NULL)
return0;
returnN->height;
}
intmax(inta, intb)
{
return(a > b)? a : b;
}
structNode* newNode(intkey)
{
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
OUTPUT:
Deletion:
#include<stdio.h>
#include<stdlib.h>
structNode
{
intkey;
structNode *left;
structNode *right;
intheight;
};
intmax(inta, intb);
intheight(structNode *N)
{
if(N == NULL)
return0;
returnN->height;
}
intmax(inta, intb)
{
return(a > b)? a : b;
}
structNode* newNode(intkey)
{
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
structNode* node = (structNode*)
malloc(sizeof(structNode));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
structNode *rightRotate(structNode *y)
{
structNode *x = y->left;
structNode *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
returnx;
}
structNode *leftRotate(structNode *x)
{
structNode *y = x->right;
structNode *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
returny;
}
intgetBalance(structNode *N)
{
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
structNode* node = (structNode*)
malloc(sizeof(structNode));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
structNode *rightRotate(structNode *y)
{
structNode *x = y->left;
structNode *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
returnx;
}
structNode *leftRotate(structNode *x)
{
structNode *y = x->right;
structNode *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
returny;
}
intgetBalance(structNode *N)
{
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
if(N == NULL)
return0;
returnheight(N->left) - height(N->right);
}
structNode* insert(structNode* node, intkey)
{
if(node == NULL)
return(newNode(key));
if(key < node->key)
node->left = insert(node->left, key);
elseif(key > node->key)
node->right = insert(node->right, key);
else
returnnode;
node->height = 1 + max(height(node->left),
height(node->right));
intbalance = getBalance(node);
if(balance > 1 && key < node->left->key)
returnrightRotate(node);
if(balance < -1 && key > node->right->key)
returnleftRotate(node);
if(balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
returnrightRotate(node);
}
if(balance < -1 && key < node->right->key)
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
if(N == NULL)
return0;
returnheight(N->left) - height(N->right);
}
structNode* insert(structNode* node, intkey)
{
if(node == NULL)
return(newNode(key));
if(key < node->key)
node->left = insert(node->left, key);
elseif(key > node->key)
node->right = insert(node->right, key);
else
returnnode;
node->height = 1 + max(height(node->left),
height(node->right));
intbalance = getBalance(node);
if(balance > 1 && key < node->left->key)
returnrightRotate(node);
if(balance < -1 && key > node->right->key)
returnleftRotate(node);
if(balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
returnrightRotate(node);
}
if(balance < -1 && key < node->right->key)
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
{
node->right = rightRotate(node->right);
returnleftRotate(node);
}
returnnode;
}
structNode * minValueNode(structNode* node)
{
structNode* current = node;
while(current->left != NULL)
current = current->left;
returncurrent;
}
structNode* deleteNode(structNode* root, intkey)
{
if(root == NULL)
return root;
if( key < root->key )
root->left = deleteNode(root->left, key);
elseif( key > root->key )
root->right = deleteNode(root->right, key);
else
{
if( (root->left == NULL) || (root->right == NULL) )
{
structNode *temp = root->left ? root->left : root->right;
if(temp == NULL)
{
temp = root;
root = NULL;
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
{
node->right = rightRotate(node->right);
returnleftRotate(node);
}
returnnode;
}
structNode * minValueNode(structNode* node)
{
structNode* current = node;
while(current->left != NULL)
current = current->left;
returncurrent;
}
structNode* deleteNode(structNode* root, intkey)
{
if(root == NULL)
return root;
if( key < root->key )
root->left = deleteNode(root->left, key);
elseif( key > root->key )
root->right = deleteNode(root->right, key);
else
{
if( (root->left == NULL) || (root->right == NULL) )
{
structNode *temp = root->left ? root->left : root->right;
if(temp == NULL)
{
temp = root;
root = NULL;
}
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
*root = *temp;
free(temp);
}
else
{
structNode* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if(root == NULL)
returnroot;
root->height = 1 + max(height(root->left),
height(root->right));
intbalance = getBalance(root);
if(balance > 1 && getBalance(root->left) >= 0)
returnrightRotate(root);
if(balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
returnrightRotate(root);
}
if(balance < -1 && getBalance(root->right) <= 0)
returnleftRotate(root);
if(balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
returnleftRotate(root);
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
*root = *temp;
free(temp);
}
else
{
structNode* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if(root == NULL)
returnroot;
root->height = 1 + max(height(root->left),
height(root->right));
intbalance = getBalance(root);
if(balance > 1 && getBalance(root->left) >= 0)
returnrightRotate(root);
if(balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
returnrightRotate(root);
}
if(balance < -1 && getBalance(root->right) <= 0)
returnleftRotate(root);
if(balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
returnleftRotate(root);
}
Paraphrase This Document
Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
returnroot;
}
voidpreOrder(structNode *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
intmain()
{
structNode *root = NULL;
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
printf("Preorder traversal of the constructed AVL "
"tree is \n");
preOrder(root);
root = deleteNode(root, 10);
printf("\nPreorder traversal after deletion of 10 \n");
preOrder(root);
return0;
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
returnroot;
}
voidpreOrder(structNode *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
intmain()
{
structNode *root = NULL;
root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
printf("Preorder traversal of the constructed AVL "
"tree is \n");
preOrder(root);
root = deleteNode(root, 10);
printf("\nPreorder traversal after deletion of 10 \n");
preOrder(root);
return0;
}
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
OUTPUT:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
OUTPUT:
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-4
Aim:Write a program to implement tree traversal in tree.
Program:
Tree Traversals (Inorder, Preorder and Postorder)
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void printPostorder(struct node* node)
{
if (node == NULL)
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-4
Aim:Write a program to implement tree traversal in tree.
Program:
Tree Traversals (Inorder, Preorder and Postorder)
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void printPostorder(struct node* node)
{
if (node == NULL)
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
return;
printPostorder(node->left);
printPostorder(node->right);
printf("%d ", node->data);
}
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
void printPreorder(struct node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
return;
printPostorder(node->left);
printPostorder(node->right);
printf("%d ", node->data);
}
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
void printPreorder(struct node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("\nPreorder traversal of binary tree is \n");
printPreorder(root);
printf("\nInorder traversal of binary tree is \n");
printInorder(root);
printf("\nPostorder traversal of binary tree is \n");
printPostorder(root);
getchar();
return 0;
}
OUTPUT:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("\nPreorder traversal of binary tree is \n");
printPreorder(root);
printf("\nInorder traversal of binary tree is \n");
printInorder(root);
printf("\nPostorder traversal of binary tree is \n");
printPostorder(root);
getchar();
return 0;
}
OUTPUT:
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-5
Aim:Write a program to implement Divide and Conqure method to find the maximum and
minimum of N elements.
Program:
Divide and Conqure method
#include<stdio.h>
#include<stdio.h>
int max, min;
int a[100];
void maxmin(int i, int j)
{
int max1, min1, mid;
if(i==j)
{
max = min = a[i];
}
else
{
if(i == j-1)
{
if(a[i] <a[j])
{
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-5
Aim:Write a program to implement Divide and Conqure method to find the maximum and
minimum of N elements.
Program:
Divide and Conqure method
#include<stdio.h>
#include<stdio.h>
int max, min;
int a[100];
void maxmin(int i, int j)
{
int max1, min1, mid;
if(i==j)
{
max = min = a[i];
}
else
{
if(i == j-1)
{
if(a[i] <a[j])
{
Paraphrase This Document
Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
max = a[j];
min = a[i];
}
else
{
max = a[i];
min = a[j];
}
}
else
{
mid = (i+j)/2;
maxmin(i, mid);
max1 = max; min1 = min;
maxmin(mid+1, j);
if(max <max1)
max = max1;
if(min > min1)
min = min1;
}
}
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
max = a[j];
min = a[i];
}
else
{
max = a[i];
min = a[j];
}
}
else
{
mid = (i+j)/2;
maxmin(i, mid);
max1 = max; min1 = min;
maxmin(mid+1, j);
if(max <max1)
max = max1;
if(min > min1)
min = min1;
}
}
}
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
int main ()
{
int i, num;
printf ("\nEnter the total number of numbers : ");
scanf ("%d",&num);
printf ("Enter the numbers : \n");
for (i=1;i<=num;i++)
scanf ("%d",&a[i]);
max = a[0];
min = a[0];
maxmin(1, num);
printf ("Minimum element in an array : %d\n", min);
printf ("Maximum element in an array : %d\n", max);
return 0;
}
OUTPUT:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
int main ()
{
int i, num;
printf ("\nEnter the total number of numbers : ");
scanf ("%d",&num);
printf ("Enter the numbers : \n");
for (i=1;i<=num;i++)
scanf ("%d",&a[i]);
max = a[0];
min = a[0];
maxmin(1, num);
printf ("Minimum element in an array : %d\n", min);
printf ("Maximum element in an array : %d\n", max);
return 0;
}
OUTPUT:
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-6
Aim: Write a program in C to implement Breadth First Search.
Program:
#include<stdio.h>
int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1;
void bfs(int v) {
for(i = 1; i <= n; i++)
if(a[v][i] && !visited[i])
q[++r] = i;
if(f <= r) {
visited[q[f]] = 1;
bfs(q[f++]);
}
}
void main() {
int v;
printf("\n Enter the number of vertices:");
scanf("%d", &n);
for(i=1; i <= n; i++) {
q[i] = 0;
visited[i] = 0;
}
printf("\n Enter graph data in matrix form:\n");
for(i=1; i<=n; i++) {
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-6
Aim: Write a program in C to implement Breadth First Search.
Program:
#include<stdio.h>
int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1;
void bfs(int v) {
for(i = 1; i <= n; i++)
if(a[v][i] && !visited[i])
q[++r] = i;
if(f <= r) {
visited[q[f]] = 1;
bfs(q[f++]);
}
}
void main() {
int v;
printf("\n Enter the number of vertices:");
scanf("%d", &n);
for(i=1; i <= n; i++) {
q[i] = 0;
visited[i] = 0;
}
printf("\n Enter graph data in matrix form:\n");
for(i=1; i<=n; i++) {
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
for(j=1;j<=n;j++) {
scanf("%d", &a[i][j]);
}
}
printf("\n Enter the starting vertex:");
scanf("%d", &v);
bfs(v);
printf("\n The node which are reachable are:\n");
for(i=1; i <= n; i++) {
if(visited[i])
printf("%d\t", i);
else {
printf("\n Bfs is not possible. Not all nodes are reachable");
break;
}
}
}
OUTPUT:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
for(j=1;j<=n;j++) {
scanf("%d", &a[i][j]);
}
}
printf("\n Enter the starting vertex:");
scanf("%d", &v);
bfs(v);
printf("\n The node which are reachable are:\n");
for(i=1; i <= n; i++) {
if(visited[i])
printf("%d\t", i);
else {
printf("\n Bfs is not possible. Not all nodes are reachable");
break;
}
}
}
OUTPUT:
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
Practical-7
Aim: Write a program to implement DFS (Depth-First Search).
Program:
DFS(Depth-First Search)
#include<stdio.h>
void DFS(int);
int G[10][10],visited[10],n; //n is no of vertices and graph is sorted in array G[10][10]
void main()
{
int i,j;
printf("Enter number of vertices:");
scanf("%d",&n);
printf("\lEnter adjecency matrix of the graph:");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
for(i=0;i<n;i++)
visited[i]=0;
DFS(0);
}
void DFS(int i)
{
int j;
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
Practical-7
Aim: Write a program to implement DFS (Depth-First Search).
Program:
DFS(Depth-First Search)
#include<stdio.h>
void DFS(int);
int G[10][10],visited[10],n; //n is no of vertices and graph is sorted in array G[10][10]
void main()
{
int i,j;
printf("Enter number of vertices:");
scanf("%d",&n);
printf("\lEnter adjecency matrix of the graph:");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
for(i=0;i<n;i++)
visited[i]=0;
DFS(0);
}
void DFS(int i)
{
int j;
Paraphrase This Document
Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
printf("\n%d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}
OUTPUT:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
printf("\n%d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}
OUTPUT:
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
Practical-8
Aim: Write a program in C to create a minimum Spanning Tree using Kruskal’s and
prime’s algorithm.
Program:
Krushkal’s algorithm
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
inti,j,k,a,b,u,v,n,ne=1;
intmin,mincost=0,cost[9][9],parent[9];
int find(int);
intuni(int,int);
void main()
{
clrscr();
printf("\n\tImplementation of Kruskal's Algorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
Practical-8
Aim: Write a program in C to create a minimum Spanning Tree using Kruskal’s and
prime’s algorithm.
Program:
Krushkal’s algorithm
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
inti,j,k,a,b,u,v,n,ne=1;
intmin,mincost=0,cost[9][9],parent[9];
int find(int);
intuni(int,int);
void main()
{
clrscr();
printf("\n\tImplementation of Kruskal's Algorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne < n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j <= n;j++)
{
if(cost[i][j] < min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
getch();
}
int find(inti)
{
while(parent[i])
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne < n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j <= n;j++)
{
if(cost[i][j] < min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
getch();
}
int find(inti)
{
while(parent[i])
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
i=parent[i];
return i;
}
intuni(inti,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
Output
Enter no. of vertices:6
Enter the adjacency matrix:
0 3 1 6 0 0
3 0 5 0 3 0
1 5 0 5 6 4
6 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
Prim’s algorithm
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
i=parent[i];
return i;
}
intuni(inti,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
Output
Enter no. of vertices:6
Enter the adjacency matrix:
0 3 1 6 0 0
3 0 5 0 3 0
1 5 0 5 6 4
6 0 5 0 0 2
0 3 6 0 0 6
0 0 4 2 6 0
Prim’s algorithm
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
#include<stdio.h>
#include<stdlib.h>
#define infinity 9999
#define MAX 20
int G[MAX][MAX],spanning[MAX][MAX],n;
int prims();
int main()
{
inti,j,total_cost;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
total_cost=prims();
printf("\nspanning tree matrix:\n");
for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf("%d\t",spanning[i][j]);
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
#include<stdio.h>
#include<stdlib.h>
#define infinity 9999
#define MAX 20
int G[MAX][MAX],spanning[MAX][MAX],n;
int prims();
int main()
{
inti,j,total_cost;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
total_cost=prims();
printf("\nspanning tree matrix:\n");
for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf("%d\t",spanning[i][j]);
}
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
printf("\n\nTotal cost of spanning tree=%d",total_cost);
return 0;
}
int prims()
{
int cost[MAX][MAX];
intu,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j;
//create cost[][] matrix,spanning[][]
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(G[i][j]==0)
cost[i][j]=infinity;
else
cost[i][j]=G[i][j];
spanning[i][j]=0;
}
//initialise visited[],distance[] and from[]
distance[0]=0;
visited[0]=1;
for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
printf("\n\nTotal cost of spanning tree=%d",total_cost);
return 0;
}
int prims()
{
int cost[MAX][MAX];
intu,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j;
//create cost[][] matrix,spanning[][]
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(G[i][j]==0)
cost[i][j]=infinity;
else
cost[i][j]=G[i][j];
spanning[i][j]=0;
}
//initialise visited[],distance[] and from[]
distance[0]=0;
visited[0]=1;
for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
}
Paraphrase This Document
Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
min_cost=0; //cost of spanning tree
no_of_edges=n-1; //no. of edges to be added
while(no_of_edges>0)
{
//find the vertex at minimum distance from the tree
min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0&&distance[i]<min_distance)
{
v=i;
min_distance=distance[i];
}
u=from[v];
//insert the edge in spanning tree
spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges--;
visited[v]=1;
//updated the distance[] array
for(i=1;i<n;i++)
if(visited[i]==0&&cost[i][v]<distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}
min_cost=min_cost+cost[u][v];
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
min_cost=0; //cost of spanning tree
no_of_edges=n-1; //no. of edges to be added
while(no_of_edges>0)
{
//find the vertex at minimum distance from the tree
min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0&&distance[i]<min_distance)
{
v=i;
min_distance=distance[i];
}
u=from[v];
//insert the edge in spanning tree
spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges--;
visited[v]=1;
//updated the distance[] array
for(i=1;i<n;i++)
if(visited[i]==0&&cost[i][v]<distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}
min_cost=min_cost+cost[u][v];
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
}
return(min_cost);
}
OUTPUT:
spanning tree matrix:
0 3 1 0 0 0
3 0 0 0 3 0
1 0 0 0 0 4
0 0 0 0 0 2
0 3 0 0 0 0
0 0 4 2 0 0
Total cost of spanning tree=13
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No.T0920CE024 Page No.
}
return(min_cost);
}
OUTPUT:
spanning tree matrix:
0 3 1 0 0 0
3 0 0 0 3 0
1 0 0 0 0 4
0 0 0 0 0 2
0 3 0 0 0 0
0 0 4 2 0 0
Total cost of spanning tree=13
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-9
Aim:Write a program to implement Factorial of N numbers.
Program:
Factorial
#include <stdio.h>
int main()
{
int n, i;
unsigned long long factorial = 1;
printf("Enter an integer: ");
scanf("%d",&n);
if (n < 0)
printf("Error! Factorial of a negative number doesn't exist.");
else
{
for(i=1; i<=n; ++i)
{
factorial *= i;
}
printf("Factorial of %d = %llu", n, factorial);
}
return 0;
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-9
Aim:Write a program to implement Factorial of N numbers.
Program:
Factorial
#include <stdio.h>
int main()
{
int n, i;
unsigned long long factorial = 1;
printf("Enter an integer: ");
scanf("%d",&n);
if (n < 0)
printf("Error! Factorial of a negative number doesn't exist.");
else
{
for(i=1; i<=n; ++i)
{
factorial *= i;
}
printf("Factorial of %d = %llu", n, factorial);
}
return 0;
}
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
OUTPUT:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
OUTPUT:
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-10
Aim:Implement the Rabin-Krap matcher and Boyer Moore Strings matching algorithms.
Program:
Rabin-krap matcher algorithm
#include<stdio.h>
#include<string.h>
#define d 256
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
for (i = 0; i < M-1; i++)
h = (h*d)%q;
for (i = 0; i < M; i++)
{
p = (d*p + pat[i])%q;
t = (d*t + txt[i])%q;
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Practical-10
Aim:Implement the Rabin-Krap matcher and Boyer Moore Strings matching algorithms.
Program:
Rabin-krap matcher algorithm
#include<stdio.h>
#include<string.h>
#define d 256
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
for (i = 0; i < M-1; i++)
h = (h*d)%q;
for (i = 0; i < M; i++)
{
p = (d*p + pat[i])%q;
t = (d*t + txt[i])%q;
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
}
for (i = 0; i <= N - M; i++)
{
if ( p == t )
{
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M)
printf("Pattern found at index %d \n", i);
}
if ( i < N-M )
{
t = (d*(t - txt[i]*h) + txt[i+M])%q;
if (t < 0)
t = (t + q);
}
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
}
for (i = 0; i <= N - M; i++)
{
if ( p == t )
{
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M)
printf("Pattern found at index %d \n", i);
}
if ( i < N-M )
{
t = (d*(t - txt[i]*h) + txt[i+M])%q;
if (t < 0)
t = (t + q);
}
Paraphrase This Document
Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
}
}
int main()
{
char txt[] = "WELCOME TO HOME";
char pat[] = "HOME";
int q = 101; // A prime number
search(pat, txt, q);
return 0;
}
OUTPUT:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
}
}
int main()
{
char txt[] = "WELCOME TO HOME";
char pat[] = "HOME";
int q = 101; // A prime number
search(pat, txt, q);
return 0;
}
OUTPUT:
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Boyer Moore Strings matching algorithm
#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256
void badCharHeuristic( string str, int size,
int badchar[NO_OF_CHARS])
{
int i;
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
void search( string txt, string pat)
{
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
badCharHeuristic(pat, m, badchar);
int s = 0;
while(s <= (n - m))
{
int j = m - 1;
while(j >= 0 && pat[j] == txt[s + j])
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
Boyer Moore Strings matching algorithm
#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256
void badCharHeuristic( string str, int size,
int badchar[NO_OF_CHARS])
{
int i;
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
void search( string txt, string pat)
{
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
badCharHeuristic(pat, m, badchar);
int s = 0;
while(s <= (n - m))
{
int j = m - 1;
while(j >= 0 && pat[j] == txt[s + j])
PARUL UNIVERSITY-FACULTY OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
j--;
if (j < 0)
{
cout <<"pattern occurs at shift = "<< s << endl;
s += (s + m < n)? m-badchar[txt[s + m]] : 1;
}
else
s += max(1, j - badchar[txt[s + j]]);
}
}
int main()
{
string txt= "ABAAABCD";
string pat = "ABC";
search(txt, pat);
return 0;
}
OUTPUT:
DEPARTMENT OF COMPUTER SCIENCE ENGINEERING
M.TECH- Computer Science Engineering
Subject: 203202102 (Advanced Data Structures) M.Tech- CSE- 1st Semester
Enrollment No. T0920CE024 Page No.
j--;
if (j < 0)
{
cout <<"pattern occurs at shift = "<< s << endl;
s += (s + m < n)? m-badchar[txt[s + m]] : 1;
}
else
s += max(1, j - badchar[txt[s + j]]);
}
}
int main()
{
string txt= "ABAAABCD";
string pat = "ABC";
search(txt, pat);
return 0;
}
OUTPUT:
1 out of 46
![[object Object]](/_next/image/?url=%2F_next%2Fstatic%2Fmedia%2Flogo.6d15ce61.png&w=640&q=75){kind=small}
Your All-in-One AI-Powered Toolkit for Academic Success.
+13062052269
info@desklib.com
Available 24*7 on WhatsApp / Email
![[object Object]](/_next/static/media/star-bottom.7253800d.svg)
Unlock your academic potential
© 2024 | Zucol Services PVT LTD | All rights reserved.