M.Tech 1st Sem: Advanced Data Structures Lab Experiments

Verified

Added on 2021/03/15

AI Summary

This document presents the lab assignments completed by Hardika Jadeja for the Advanced Data Structures course (203202102) at Parul University, Faculty of Engineering & Technology, during the M.Tech 1st semester of the academic year 2020-21. The assignments cover a range of fundamental data structures and algorithms, including factors influencing space complexity, factorial calculation (recursive and non-recursive), parenthesis matching using stacks, implementation of insertion and deletion in AVL trees, tree traversal algorithms (inorder, preorder, postorder), divide and conquer method for finding minimum and maximum, breadth-first search (BFS), depth-first search (DFS), minimum spanning tree using Kruskal's and Prim's algorithms, and string matching algorithms (Rabin-Karp and Boyer Moore). Each experiment includes the aim, program code written in C, and the corresponding output, demonstrating a practical understanding of these core concepts. The document serves as a comprehensive record of the student's laboratory work and provides valuable insights into the practical application of advanced data structures.

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:...........................................

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 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();
}

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.
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.
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()
{

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:

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;
}

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.
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);