DMI COLLEGE OF ENGINEERING

(AN AUTONOMOUS INSTITUTION)

(Affiliated to Anna University, Chennai-600 025)

Palanchur, Chennai–600123

REG.NO:………………………………………..

NAME:………………………………….………

CP4161- ADVANCED DATA STRUCTURES AND ALGORITHMS LABORATORY

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

I YEAR / I SEMESTER
2024-2025
 DMI COLLEGE OF ENGINEERING
Mevalurkuppam, “B‟Village, Palanchur, Nazarathpet Post,
Chennai-600123

BONAFIDE CERTIFICATE
UNIVERSITY REGISTER NUMBER :

Certified that this is bonafide record of practical work done by

Mr./Ms. ……………………………………………...of ……………………….…..

Department in the……………………………………………........... Laboratory during

the Semester….……….Year………………..and submitted for the University

Practical Examination conducted on …………………at DMI College of Engineering,

Palanchur, Chennai.

Subject In-Charge Head of the Department

Internal Examiner External Examiner

S.NO DATE NAMEOF EXPERIMENT PAGE SIGN
NO
S.NO DATE NAMEOF EXPERIMENT PAGE SIGN
NO
 EX. No. 1(A) Date: …………..
IMPLEMENTATION OF RECURSIVE FUNCTION FOR TREE
TRAVERSAL
AIM
To write a program in C++ to implement the recursive function for tree traversal.

Algorithm Inorder(tree)

1. Traverse the left subtree, i.e., call Inorder (left-subtree)

2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder (right-subtree)

Algorithm Postorder(tree)

1. Traverse the left subtree, i.e., call Postorder(left-subtree)

2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.

Algorithm Preorder(tree)

1. Visit the root.

2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)

PROGRAM

#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
/* Given a binary tree, print its nodes according to the "bottom-up" postorder traversal. */
void printPostorder(struct Node* node)
{
if (node == NULL)
return;
printPostorder(node->left);
printPostorder(node->right);
cout << node->data << " ";
}
void printInorder(struct Node* node)
{
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
void printPreorder(struct Node* node)
{
if (node == NULL)
return;
cout << node->data << " ";
printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
cout << "\nPreorder traversal of binary tree is \n";
printPreorder(root);
cout << "\nInorder traversal of binary tree is \n";
printInorder(root);
cout << "\nPostorder traversal of binary tree is \n";
printPostorder(root);
return 0;
}
OUTPUT

Preorder traversal of binary tree is

12453
Inorder traversal of binary tree is
42513
Postorder traversal of binary tree is
4 5 2 3 1 UT

RESULT:
Thus the C++ program for implementation of the recursive function for tree traversal was
created, executed and output was verified successfully.
 EX. No. 1(B) Date: …………..
IMPLEMENTATION OF RECURSIVE FUNCTION FOR FIBONACCI
AIM
To write a program in C++ to implement the recursive function for fibonacci.

DESCRIPTION

1. Function is a block of statements that performs some operations. All C++ programs
have at least one function – function called “main()”. This function is entry-point of
your program.
2. A function declaration tells the compiler about a function’s name, return type, and
parameters. A function definition provides the actual body of the function.

PROGRAM

#include<iostream>
using namespace std;
int fibonacci(int n)
{
if((n==1)||(n==0))
{
return(n);
}
else
{
return(fibonacci(n-1)+fibonacci(n-2));
}
}

int main()
{
int n,i=0;
cout<<"\nHow many terms for Fibonacci Series :: ";
cin>>n;
cout<<"\nFibonacci Series for [ "<<n<<" ] Terms as follows :: \n\n";

while(i<n)
{
cout<<" "<<fibonacci(i);
i++;
}
cout<<"\n";

return 0;
}
OUTPUT

How many terms for Fibonacci Series :: 10

Fibonacci Series for [ 10 ] Terms as follows ::
0 1 1 2 3 5 8 13 21 34
Process returned 0

RESULT:
Thus the C++ program for implementation of the recursive function for fibonacci was created,
executed and output was verified successfully.
 EX. No. 2(A) Date: …………..
IMPLEMENTATION OF ITERATION FUNCTION FOR TREE
TRAVERSAL

AIM
To write a program in C++ to implement the iteration function for tree traversal.

ALGORITHM

1) Create an empty stack nodeStack and push root node to stack.

2) Do the following while nodeStack is not empty.
a) Pop an item from the stack and print it.
b) Push right child of a popped item to stack
c) Push left child of a popped item to stack
The right child is pushed before the left child to make sure that the left subtree is processed
first.

PROGRAM

#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = new struct node;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
void iterativePreorder(node* root)
{
if (root == NULL)
return;

stack<node*> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false)
{ struct node* node =
nodeStack.top(); printf("%d ", node-
>data); nodeStack.pop();
if (node->right)
nodeStack.push(node->right);
if (node->left)
 nodeStack.push(node->left);
}
}
int main()
{
struct node* root = newNode(10);
root->left = newNode(8);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
root->right->left = newNode(2);
iterativePreorder(root);
return 0;
}

OUTPUT:

10 8 3 5 2 2

RESULT:
Thus the C++ program for implementation of iteration function for tree traversal was created,
executed and output was verified successfully.
 EX. No. Date: …………..
IMPLEMENTION OF ITERATION FUNCTION FOR FIBONACCI
AIM
To write a program in C++ to implement the Iteration function for Fibonacci.

DESCRIPTION

The following C++ computes the Nth Fibonacci Number using this equation which runs O(1)
time and O(1) space (assuming the equation computation is O(1) constant))

PROGRAM

#include <iostream>
using namespace std;
void fib(int num) {
int x = 0, y = 1, z = 0;
for (int i = 0; i < num; i++)
{ cout << x << " ";
z = x + y;
x = y;
y = z;
}
}
int main()
{ int num;
cout << "Enter the number : ";
cin >> num;
cout << "\nThe fibonacci series : " ;
fib(num);
return 0;
}

OUTPUT
Enter the number : 10
The fibonacci series : 0 1 1 2 3 5 8 13 21 34

RESULT:
Thus the C++ program for implementation of Iteration function for Fibonacci was created,
executed and output was verified successfully.
 EX. No. 3(A) Date: …………..
IMPLEMENTATION OF MERGE SORT
AIM
To write a program in C++ to implement the Implementation of Merge Sort.

DESCRIPTION

MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = l+ (r-l)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)

PROGRAM

#include <iostream>
using namespace std;
void merge(int array[], int const left, int const mid, int const right)
{
auto const subArrayOne = mid - left + 1;
auto const subArrayTwo = right - mid;

auto *leftArray = new int[subArrayOne],

*rightArray = new int[subArrayTwo];

for (auto i = 0; i < subArrayOne; i++)

leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];

auto indexOfSubArrayOne = 0, // Initial index of first sub-array

indexOfSubArrayTwo = 0; // Initial index of second sub-array
int indexOfMergedArray = left; // Initial index of merged array

while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo)

{ if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else {
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
 }
while (indexOfSubArrayOne < subArrayOne) { array[indexOfMergedArray]
= leftArray[indexOfSubArrayOne]; indexOfSubArrayOne++;
indexOfMergedArray++;
}
while (indexOfSubArrayTwo < subArrayTwo)
{ array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
}
void mergeSort(int array[], int const begin, int const end)
{
if (begin >= end)
return; // Returns recursively

auto mid = begin + (end - begin) / 2;

mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}
void printArray(int A[], int size)
{
for (auto i = 0; i < size; i++)
cout << A[i] << " ";
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
auto arr_size = sizeof(arr) / sizeof(arr[0]);

cout << "Given array is \n";

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\nSorted array is \n";

printArray(arr, arr_size);
return 0;
}
Output
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13

RESULT:
Thus the C++ program for implementation of Merge Sort was created, executed and output
was verified successfully.
 EX. No. 3(B) Date: …………..
IMPLEMENTATION OF QUICK SORT
AIM
To write a program in C++ to implement the implementation of QuickSort.

DESCRIPTION

1. Always pick the first element as a pivot (implemented below).

2. Always pick the last element as the pivot.
3. Pick a random element as a pivot.
4. Pick median as a pivot.

PROGRAM

#include <bits/stdc++.h>
using namespace std;
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
if (arr[j] < pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size)
{
 int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}

OUTPUT
Sorted array:
1 5 7 8 9 10

RESULT:
Thus the C++ program for implementation of QuickSort was created, executed and output was
verified successfully.
 EX. No. 4 Date: …………..
IMPLEMENTION OF BINARY SEARCH TREE
AIM
To write a program in C++ to implement the Binary Search Tree.

DESCRIPTION

Binary Search Tree is a node-based binary tree data structure which has the following
properties:
1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.

PROGRAM

#include <iostream>
using namespace std;
class BST {
int data;
BST *left, *right;
public:
BST();
BST(int);

BST* Insert(BST*, int);

void Inorder(BST*);
};
BST ::BST()
: data(0)
, left(NULL)
, right(NULL)
{
}
BST ::BST(int value)
{
data = value;
left = right = NULL;
}
BST* BST ::Insert(BST* root, int value)
{
if (!root) {
// Insert the first node, if root is NULL.
return new BST(value);
}

if (value > root->data) {

root->right = Insert(root->right, value);
 }
else {
root->left = Insert(root->left, value);
}
return root;
}
void BST ::Inorder(BST* root)
{
if (!root)
{ return;
}
Inorder(root->left);
cout << root->data << endl;
Inorder(root->right);
}
int main()
{
BST b, *root = NULL;
root = b.Insert(root, 50);
b.Insert(root, 30);
b.Insert(root, 20);
b.Insert(root, 40);
b.Insert(root, 70);
b.Insert(root, 60);
b.Insert(root, 80);

b.Inorder(root);
return 0;
}

OUTPUT

20
30
40
50
60
70
80
DELETION

#include <bits/stdc++.h>
using namespace std;
struct node {
int key;
struct node *left, *right;
};

struct node* newNode(int item)

{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorder(struct node* root)
{
if (root != NULL)
{ inorder(root->left);
cout << root->key;
inorder(root->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);
else
node->right = insert(node->right, key);

return node;
}
struct node* minValueNode(struct node* node)
{
struct node* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
struct node* deleteNode(struct node* root, int key)
{
if (root == NULL)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
 else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
if (root->left==NULL and root->right==NULL)
return NULL;
else if (root->left == NULL)
{ struct node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{ struct node* temp = root->left;
free(root);
return temp;
}
struct node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
int main()
{
struct node* root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
cout << "Inorder traversal of the given tree \n";
inorder(root);
cout << "\nDelete 20\n";
root = deleteNode(root, 20);
cout << "Inorder traversal of the modified tree \n";
inorder(root);
cout << "\nDelete 30\n";
root = deleteNode(root, 30);
cout << "Inorder traversal of the modified tree \n";
inorder(root);
cout << "\nDelete 50\n";
root = deleteNode(root, 50);
cout << "Inorder traversal of the modified tree \n";
inorder(root);

return 0;
}
OUTPUT:

Inorder traversal of the given tree

20 30 40 50 60 70 80
Delete 20
Inorder traversal of the modified tree
30 40 50 60 70 80
Delete 30
Inorder traversal of the modified tree
40 50 60 70 80
Delete 50
Inorder traversal of the modified tree
40 60 70 80

RESULT:
Thus the C++ program for implementation of Binary Search Tree was created, executed and
output was verified successfully.
 EX. No. 5 Date: …………..
IMPLEMENTION OF RED-BLACK TREE
AIM
To write a program in C++ to implement the Red-Black Tree.

DESCRIPTION

1. A node is either red or black.

2. The root is black. (This rule is sometimes omitted. Since the root can always be changed
from red to black, but not necessarily vice versa, this rule has little effect on analysis).
3. All leaves (NIL) are black. All leaves are of the same color as the root.
4. Every red node must have two black child nodes, and therefore it must have a black parent.
5. Every path from a given node to any of its descendant NIL nodes contains the same
number of black nodes.

PROGRAM

#include<iostream>
using namespace std;
struct node
{
int key;
node *parent;
char color;
node *left;
node *right;
};
class RBtree
{
node *root;
node *q;
public :
RBtree()
{
q=NULL;
root=NULL;
}
void insert();
void insertfix(node *);
void leftrotate(node *);
void rightrotate(node *);
void del();
node* successor(node *);
void delfix(node *);
void disp();
void display( node *);
void search();
};
void RBtree::insert()
{
int z,i=0;
cout<<"\nEnter key of the node to be inserted: ";
cin>>z;
node *p,*q;
node *t=new node;
t->key=z;
t->left=NULL;
t->right=NULL;
t->color='r';
p=root;
q=NULL;
if(root==NULL)
{
root=t;
t->parent=NULL;
}
else
{
while(p!=NULL)
{
q=p;
if(p->key<t->key)
p=p->right;
else
p=p->left;
}
t->parent=q;
if(q->key<t->key)
q->right=t;
else
q->left=t;
}
insertfix(t);
}
void RBtree::insertfix(node *t)
{
node *u;
if(root==t)
{
t->color='b';
return;
}
while(t->parent!=NULL&&t->parent->color=='r')
{
node *g=t->parent->parent;
if(g->left==t->parent)
{
if(g->right!=NULL)
 {
u=g->right;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->right==t)
{
t=t->parent;
leftrotate(t);
}
t->parent->color='b';
g->color='r';
rightrotate(g);
}
}
else
{
if(g->left!=NULL)
{
u=g->left;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->left==t)
{
t=t->parent;
rightrotate(t);
}
t->parent->color='b';
g->color='r';
leftrotate(g);
}
}
root->color='b';
}
}
void RBtree::del()
{
if(root==NULL)
{
cout<<"\nEmpty Tree." ;
return ;
}
int x;
cout<<"\nEnter the key of the node to be deleted: ";
cin>>x;
node *p;
p=root;
node *y=NULL;
node *q=NULL;
int found=0;
while(p!=NULL&&found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
{
cout<<"\nElement Not Found.";
return ;
}
else
{
cout<<"\nDeleted Element: "<<p->key;
cout<<"\nColour: ";
if(p->color=='b')
cout<<"Black\n";
else
cout<<"Red\n";

if(p->parent!=NULL)
cout<<"\nParent: "<<p->parent->key;
else
cout<<"\nThere is no parent of the node. ";
if(p->right!=NULL)
cout<<"\nRight Child: "<<p->right->key;
else
cout<<"\nThere is no right child of the node. ";
 if(p->left!=NULL)
cout<<"\nLeft Child: "<<p->left->key;
else
cout<<"\nThere is no left child of the node. ";
cout<<"\nNode Deleted.";
if(p->left==NULL||p->right==NULL)
y=p;
else
y=successor(p);
if(y->left!=NULL)
q=y->left;
else
{
if(y->right!=NULL)
q=y->right;
else
q=NULL;
}
if(q!=NULL)
q->parent=y->parent;
if(y->parent==NULL)
root=q;
else
{
if(y==y->parent->left)
y->parent->left=q;
else
y->parent->right=q;
}
if(y!=p)
{
p->color=y->color;
p->key=y->key;
}
if(y->color=='b')
delfix(q);
}
}

void RBtree::delfix(node *p)

{
node *s;
while(p!=root&&p->color=='b')
{
if(p->parent->left==p)
{
s=p->parent->right;
if(s->color=='r')
{
s->color='b';
 p->parent->color='r';
leftrotate(p->parent);
s=p->parent->right;
}
if(s->right->color=='b'&&s->left->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->right->color=='b')
{
s->left->color=='b';
s->color='r';
rightrotate(s);
s=p->parent->right;
}
s->color=p->parent->color;
p->parent->color='b';
s->right->color='b';
leftrotate(p->parent);
p=root;
}
}
else
{
s=p->parent->left;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
rightrotate(p->parent);
s=p->parent->left;
}
if(s->left->color=='b'&&s->right->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->left->color=='b')
{
s->right->color='b';
s->color='r';
leftrotate(s);
s=p->parent->left;
}
s->color=p->parent->color;
 p->parent->color='b';
s->left->color='b';
rightrotate(p->parent);
p=root;
}
}
p->color='b';
root->color='b';
}
}

void RBtree::leftrotate(node *p)

{
if(p->right==NULL)
return ;
else
{
node *y=p->right;
if(y->left!=NULL)
{
p->right=y->left;
y->left->parent=p;
}
else
p->right=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->left=p;
p->parent=y;
}
}
void RBtree::rightrotate(node *p)
{
if(p->left==NULL)
return ;
else
{
node *y=p->left;
if(y->right!=NULL)
{
p->left=y->right;
 y->right->parent=p;
}
else
p->left=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->right=p;
p->parent=y;
}
}

node* RBtree::successor(node *p)

{
node *y=NULL;
if(p->left!=NULL)
{
y=p->left;
while(y->right!=NULL)
y=y->right;
}
else
{
y=p->right;
while(y->left!=NULL)
y=y->left;
}
return y;
}

void RBtree::disp()
{
display(root);
}
void RBtree::display(node *p)
{
if(root==NULL)
{
cout<<"\nEmpty Tree.";
return ;
}
if(p!=NULL)
 {
cout<<"\n\t NODE: ";
cout<<"\n Key: "<<p->key;
cout<<"\n Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<"\n Parent: "<<p->parent->key;
else
cout<<"\n There is no parent of the node. ";
if(p->right!=NULL)
cout<<"\n Right Child: "<<p->right->key;
else
cout<<"\n There is no right child of the node. ";
if(p->left!=NULL)
cout<<"\n Left Child: "<<p->left->key;
else
cout<<"\n There is no left child of the node. ";
cout<<endl;
if(p->left)
{
cout<<"\n\nLeft:\n";
display(p->left);
}
/*else
cout<<"\nNo Left Child.\n";*/
if(p->right)
{
cout<<"\n\nRight:\n";
display(p->right);
}
/*else
cout<<"\nNo Right Child.\n"*/
}
}
void RBtree::search()
{
if(root==NULL)
{
cout<<"\nEmpty Tree\n" ;
return ;
}
int x;
cout<<"\n Enter key of the node to be searched: ";
cin>>x;
node *p=root;
int found=0;
while(p!=NULL&& found==0)
 {
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
cout<<"\nElement Not Found.";
else
{
cout<<"\n\t FOUND NODE: ";
cout<<"\n Key: "<<p->key;
cout<<"\n Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<"\n Parent: "<<p->parent->key;
else
cout<<"\n There is no parent of the node. ";
if(p->right!=NULL)
cout<<"\n Right Child: "<<p->right->key;
else
cout<<"\n There is no right child of the node. ";
if(p->left!=NULL)
cout<<"\n Left Child: "<<p->left->key;
else
cout<<"\n There is no left child of the node. ";
cout<<endl;

}
}
int main()
{
int ch,y=0;
RBtree obj;
do
{
cout<<"\n\t RED BLACK TREE " ;
cout<<"\n 1. Insert in the tree ";
cout<<"\n 2. Delete a node from the tree";
cout<<"\n 3. Search for an element in the tree";
cout<<"\n 4. Display the tree ";
cout<<"\n 5. Exit " ;
 cout<<"\nEnter Your Choice: ";
cin>>ch;
switch(ch)
{
case 1 : obj.insert();
cout<<"\nNode Inserted.\n";
break;
case 2 : obj.del();
break;
case 3 : obj.search();
break;
case 4 : obj.disp();
break;
case 5 : y=1;
break;
default : cout<<"\nEnter a Valid Choice.";
}
cout<<endl;

}while(y!=1);
return 1;
}
OUTPUT

RESULT:
Thus the C++ program for implementation of the Red-Black Tree was created, executed and
output was verified successfully.
 EX. No. 6 Date: …………..
IMPLEMENTION OF HEAP
AIM
To write a program in C++ to implement the Heap Implementation.

DESCRIPTION

A Binary Heap is a Binary Tree with following properties.

1) It’s a complete tree (All levels are completely filled except possibly the last level and the
last level has all keys as left as possible). This property of Binary Heap makes them suitable
to be stored in an array.

2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root
must be minimum among all keys present in Binary Heap. The same property must be
recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

PROGRAM

#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
class BHeap {
private:
vector <int> heap;
int l(int parent);
int r(int parent);
int par(int child);
void heapifyup(int index);
void heapifydown(int index);
public:
BHeap() {}
void Insert(int element);
void DeleteMin();
int ExtractMin();
void showHeap();
int Size();
};
int main()
{ BHeap h;
while (1) {
cout<<"1.Insert Element"<<endl;
cout<<"2.Delete Minimum Element"<<endl;
cout<<"3.Extract Minimum Element"<<endl;
cout<<"4.Show Heap"<<endl;
cout<<"5.Exit"<<endl;
int c, e;
 cout<<"Enter your choice: ";
cin>>c;
switch(c)
{ case 1:
cout<<"Enter the element to be inserted: ";
cin>>e;
h.Insert(e);
break;
case 2:
h.DeleteMin();
break;
case 3:
if (h.ExtractMin() == -1)
{ cout<<"Heap is Empty"<<endl;
}
else
cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
break;
case 4:
cout<<"Displaying elements of Hwap: ";
h.showHeap();
break;
case 5:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
} }
return 0;
}
int BHeap::Size()
{ return
heap.size();
}
void BHeap::Insert(int ele)
{ heap.push_back(ele);
heapifyup(heap.size() -1);
}
void BHeap::DeleteMin()
{ if (heap.size() == 0) {
cout<<"Heap is Empty"<<endl;
return;
}
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
cout<<"Element Deleted"<<endl;
}
int BHeap::ExtractMin()
{ if (heap.size() == 0) {
return -1;
}
 else
return heap.front();
}
void BHeap::showHeap() {
vector <int>::iterator pos = heap.begin();
cout<<"Heap --> ";
while (pos != heap.end())
{ cout<<*pos<<" ";
pos++;
}
cout<<endl;
}
int BHeap::l(int parent)
{ int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;}
int BHeap::r(int parent)
{ int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;}
int BHeap::par(int child)
{ int p = (child - 1)/2;
if (child == 0)
return -1;
else
return p;}
void BHeap::heapifyup(int in) {
if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in])
{ int temp = heap[in];
heap[in] = heap[par(in)];
heap[par(in)] = temp;
heapifyup(par(in));
}}
void BHeap::heapifydown(int in)
{ int child = l(in);
int child1 = r(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1])
{ child = child1; }
if (child > 0 && heap[in] > heap[child])
{ int t = heap[in];
heap[in] = heap[child];
heap[child] = t;
heapifydown(child);
}
}
OUTPUT
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 2
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 3
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 7
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 6
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 2 3 7 6
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 3
Minimum Element: 2
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 3
Minimum Element: 2
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 2
Element Deleted
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 3 6 7
1. Insert Element
2. Delete Minimum Element
3. Extract Minimum Element
4. Show Heap
5.Exit
Enter your choice: 5

RESULT:
Thus the C++ program for implementation of Heap was created, executed and output was
verified successfully.
 EX. No. 7 Date: …………..
IMPLEMENTION OF FIBONACCI HEAP
AIM
To write a program in C++ to implement the Fibonacci Heap.

DESCRIPTION

1. It is a set of min heap-ordered trees. (i.e. The parent is always smaller than the
children.)
2. A pointer is maintained at the minimum element node.
3. It consists of a set of marked nodes. (Decrease key operation)
4. The trees within a Fibonacci heap are unordered but rooted.

PROGRAM

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
struct node
{
int n;
int degree;
node* parent;
node* child;
node* left;
node* right;
char mark;
char C;
};
class FibonacciHeap
{
private:
int nH;
node *H;
public:
node* InitializeHeap();
int Fibonnaci_link(node*, node*, node*);
node *Create_node(int);
node *Insert(node *, node *);
node *Union(node *, node *);
node *Extract_Min(node *);
int Consolidate(node *);
int Display(node *);
node *Find(node *, int);
int Decrease_key(node *, int, int);
int Delete_key(node *,int);
int Cut(node *, node *, node *);
int Cascase_cut(node *, node *);
 FibonacciHeap()
{
H = InitializeHeap();
}
};
node* FibonacciHeap::InitializeHeap()
{
node* np;
np = NULL;
return np;
}

node* FibonacciHeap::Create_node(int value)

{
node* x = new node;
x->n = value;
return x;
}
node* FibonacciHeap::Insert(node* H, node* x)
{
x->degree = 0;
x->parent = NULL;
x->child = NULL;
x->left = x;
x->right = x;
x->mark = 'F';
x->C = 'N';
if (H != NULL)
{
(H->left)->right = x;
x->right = H;
x->left = H->left;
H->left = x;
if (x->n < H->n)
H = x;
}
else
{
H = x;
}
nH = nH + 1;
return H;
}
int FibonacciHeap::Fibonnaci_link(node* H1, node* y, node* z)
{
(y->left)->right = y->right;
(y->right)->left = y->left;
if (z->right == z)
H1 = z;
y->left = y;
 y->right = y;
y->parent = z;
if (z->child == NULL)
z->child = y;
y->right = z->child;
y->left = (z->child)->left;
((z->child)->left)->right = y;
(z->child)->left = y;
if (y->n < (z->child)->n)
z->child = y;
z->degree++;
}
node* FibonacciHeap::Union(node* H1, node* H2)
{
node* np;
node* H = InitializeHeap();
H = H1;
(H->left)->right = H2;
(H2->left)->right = H;
np = H->left;
H->left = H2->left;
H2->left = np;
return H;
}
int FibonacciHeap::Display(node* H)
{
node* p = H;
if (p == NULL)
{
cout<<"The Heap is Empty"<<endl;
return 0;
}
cout<<"The root nodes of Heap are: "<<endl;
do
{
cout<<p->n;
p = p->right;
if (p != H)
{
cout<<"-->";
}
}
while (p != H && p->right != NULL);
cout<<endl;
}
node* FibonacciHeap::Extract_Min(node* H1)
{
node* p;
node* ptr;
node* z = H1;
 p = z;
ptr = z;
if (z == NULL)
return z;
node* x;
node* np;
x = NULL;
if (z->child != NULL)
x = z->child;
if (x != NULL)
{
ptr = x;
do
{
np = x->right;
(H1->left)->right = x;
x->right = H1;
x->left = H1->left;
H1->left = x;
if (x->n < H1->n)
H1 = x;
x->parent = NULL;
x = np;
}
while (np != ptr);
}
(z->left)->right = z->right;
(z->right)->left = z->left;
H1 = z->right;
if (z == z->right && z->child == NULL)
H = NULL;
else
{
H1 = z->right;
Consolidate(H1);
}
nH = nH - 1;
return p;
}
int FibonacciHeap::Consolidate(node* H1)
{
int d, i;
float f = (log(nH)) / (log(2));
int D = f;
node* A[D];
for (i = 0; i <= D; i++)
A[i] = NULL;
node* x = H1;
node* y;
node* np;
node* pt = x;
do
{
pt = pt->right;
d = x->degree;
while (A[d] != NULL)
{
y = A[d];
if (x->n > y->n)
{
np = x;
x = y;
y = np;
}
if (y == H1)
H1 = x;
Fibonnaci_link(H1, y, x);
if (x->right == x)
H1 = x;
A[d] = NULL;
d = d + 1;
}
A[d] = x;
x = x->right;
}
while (x != H1);
H = NULL;
for (int j = 0; j <= D; j++)
{
if (A[j] != NULL)
{
A[j]->left = A[j];
A[j]->right =A[j];
if (H != NULL)
{
(H->left)->right = A[j];
A[j]->right = H;
A[j]->left = H->left;
H->left = A[j];
if (A[j]->n < H->n)
H = A[j];
}
else
{
H = A[j];
}
if(H == NULL)
H = A[j];
else if (A[j]->n < H->n)
H = A[j];
 }
}
}
int FibonacciHeap::Decrease_key(node*H1, int x, int k)
{
node* y;
if (H1 == NULL)
{
cout<<"The Heap is Empty"<<endl;
return 0;
}
node* ptr = Find(H1, x);
if (ptr == NULL)
{
cout<<"Node not found in the Heap"<<endl;
return 1;
}
if (ptr->n < k)
{
cout<<"Entered key greater than current key"<<endl;
return 0;
}
ptr->n = k;
y = ptr->parent;
if (y != NULL && ptr->n < y->n)
{
Cut(H1, ptr, y);
Cascase_cut(H1, y);
}
if (ptr->n < H->n)
H = ptr;
return 0;
}
int FibonacciHeap::Cut(node* H1, node* x, node* y)
{
if (x == x->right)
y->child = NULL;
(x->left)->right = x->right;
(x->right)->left = x->left;
if (x == y->child)
y->child = x->right;
y->degree = y->degree - 1;
x->right = x;
x->left = x;
(H1->left)->right = x;
x->right = H1;
x->left = H1->left;
H1->left = x;
x->parent = NULL;
x->mark = 'F';
}
int FibonacciHeap::Cascase_cut(node* H1, node* y)
{
node* z = y->parent;
if (z != NULL)
{
if (y->mark == 'F')
{
y->mark = 'T';
}
else
{
Cut(H1, y, z);
Cascase_cut(H1, z);
}
}
}
node* FibonacciHeap::Find(node* H, int k)
{
node* x = H;
x->C = 'Y';
node* p = NULL;
if (x->n == k)
{
p = x;
x->C = 'N';
return p;
}
if (p == NULL)
{
if (x->child != NULL )
p = Find(x->child, k);
if ((x->right)->C != 'Y' )
p = Find(x->right, k);
}
x->C = 'N';
return p;
}
int FibonacciHeap::Delete_key(node* H1, int k)
{
node* np = NULL;
int t;
t = Decrease_key(H1, k, -5000);
if (!t)
np = Extract_Min(H);
if (np != NULL)
cout<<"Key Deleted"<<endl;
else
cout<<"Key not Deleted"<<endl;
return 0;
}
int main()
{
int n, m, l;
FibonacciHeap fh;
node* p;
node* H;
H = fh.InitializeHeap();
while (1)
{
cout<<" "<<endl;
cout<<"Operations on Binomial heap"<<endl;
cout<<" "<<endl;
cout<<"1)Insert Element in the heap"<<endl;
cout<<"2)Extract Minimum key node"<<endl;
cout<<"3)Decrease key of a node"<<endl;
cout<<"4)Delete a node"<<endl;
cout<<"5)Display Heap"<<endl;
cout<<"6)Exit"<<endl;
cout<<"Enter Your Choice: ";
cin>>l;
switch(l)
{
case 1:
cout<<"Enter the element to be inserted: ";
cin>>m;
p = fh.Create_node(m);
H = fh.Insert(H, p);
break;
case 2:
p = fh.Extract_Min(H);
if (p != NULL)
cout<<"The node with minimum key: "<<p->n<<endl;
else
cout<<"Heap is empty"<<endl;
break;
case 3:
cout<<"Enter the key to be decreased: ";
cin>>m;
cout<<"Enter new key value: ";
cin>>l;
fh.Decrease_key(H, m, l);
break;
case 4:
cout<<"Enter the key to be deleted: ";
cin>>m;
fh.Delete_key(H, m);
break;
case 5:
cout<<"The Heap is: "<<endl;
 fh.Display(H);
break;
case 6:
exit(1);
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
OUTPUT

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 9

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 8

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 7

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 6

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 5

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 5
The Heap is:
The root nodes of Heap are:
5-->6-->7-->8-->9

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 5

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 3
Enter the key to be decreased: 3
Enter new key value: 1
Node not found in the Heap

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 3
Enter the key to be decreased: 5
Enter new key value: 2

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 2

Operations on Binomial heap

1) Insert Element in the heap

2) Extract Minimum key node
3) Decrease key of a node
4) Delete a node
5) Display Heap
6)Exit
Enter Your Choice: 6

RESULT:
Thus the C++ program for implementation of Fibonacci Heap was created, executed and output
was verified successfully.
 EX. No. 8(A) Date: …………..
GRAPH TRAVERSAL (BFS)
AIM
To write a program in C++ to implement the Graph Traversal (BFS).

DESCRIPTION

1. Start by putting any one of the graph's vertices at the back of a queue.
2. Take the front item of the queue and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited
list to the back of the queue.
4. Keep repeating steps 2 and 3 until the queue is empty.

PROGRAM

#include<bits/stdc++.h>
using namespace std;
class Graph
{
int V; // No. of vertices
vector<list<int>> adj;
public:
Graph(int V); // Constructor
void addEdge(int v, int w);
void BFS(int s);
};

Graph::Graph(int V)
{
this->V = V;
adj.resize(V);
}

void Graph::addEdge(int v, int w)

{
adj[v].push_back(w); // Add w to v’s list.
}

void Graph::BFS(int s)
{
vector<bool> visited;
visited.resize(V,false);
list<int> queue;
visited[s] = true;
queue.push_back(s);

while(!queue.empty())
{
s = queue.front();
 cout << s << " ";
queue.pop_front();
for (auto adjecent: adj[s])
{
if (!visited[adjecent])
{
visited[adjecent] = true;
queue.push_back(adjecent);
}
}
}
}
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

cout << "Following is Breadth First Traversal "

<< "(starting from vertex 2) \n";
g.BFS(2);

return 0;
}
OUTPUT

Following is Breadth First Traversal (starting from vertex 2)

2031

RESULT:
Thus the C++ program for implementation of Graph Traversal (BFS) was created, executed
and output was verified successfully.
EX. No. 8(B) Date: …………..
GRAPH TRAVERSAL (DFS)
AIM
To write a program in C++ to implement the Graph Traversal (DFS).

DESCRIPTION

1. Create a recursive function that takes the index of the node and a visited array.
2. Mark the current node as visited and print the node.
3. Traverse all the adjacent and unmarked nodes and call the recursive function with the
index of the adjacent node.

PROGRAM

#include <bits/stdc++.h>
using namespace std;
class Graph {
public:
map<int, bool> visited;
map<int, list<int> > adj;
void addEdge(int v, int w);
void DFS(int v);
};
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

void Graph::DFS(int v)
{
visited[v] = true;
cout << v << " ";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFS(*i);
}

int main()
{
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
 cout << "Following is Depth First Traversal"
" (starting from vertex 2) \n";
g.DFS(2);

return 0;
}

OUTPUT:

Following is Depth First Traversal (starting from vertex 2)

2013

RESULT:
Thus the C++ program for implementation of Graph Traversal (DFS) was created, executed
and output was verified successfully.
 EX. No. 9 Date: …………..
IMPLEMENTION OF SPANNING TREE
AIM
To write a program in C++ to implement the Spanning Tree.

DESCRIPTION

1. Sort all the edges in non-decreasing order of their weight.

2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If
cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

PROGRAM

#include <bits/stdc++.h>
using namespace std;
class DSU {
int* parent;
int* rank;
public:
DSU(int n)
{
parent = new int[n];
rank = new int[n];

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

{ parent[i] = -1;
rank[i] = 1;
}
}
int find(int i)
{
if (parent[i] == -1)
return i;

return parent[i] = find(parent[i]);

}
void unite(int x, int y)
{
int s1 = find(x);
int s2 = find(y);

if (s1 != s2) {
if (rank[s1] < rank[s2])
{ parent[s1] = s2;
rank[s2] += rank[s1];
}
 else {
parent[s2] = s1;
rank[s1] += rank[s2];
}
}
}
};

class Graph
{ vector<vector<int> >
edgelist; int V;

public:
Graph(int V) { this->V = V; }

void addEdge(int x, int y, int w)

{
edgelist.push_back({ w, x, y });
}

void kruskals_mst()
{
sort(edgelist.begin(), edgelist.end());
DSU s(V);
int ans = 0;
cout << "Following are the edges in the "
"constructed MST"
<< endl;
for (auto edge : edgelist)
{ int w = edge[0];
int x = edge[1];
int y = edge[2];
if (s.find(x) != s.find(y))
{ s.unite(x, y);
ans += w;
cout << x << " -- " << y << " == " << w
<< endl;
}
}
cout << "Minimum Cost Spanning Tree: " << ans;
}
};
int main()
{
Graph g(4);
g.addEdge(0, 1, 10);
g.addEdge(1, 3, 15);
g.addEdge(2, 3, 4);
g.addEdge(2, 0, 6);
g.addEdge(0, 3, 5);
}
g.kruskals_mst();
return 0;
}

OUTPUT

Following are the edges in the constructed MST

2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19

RESULT:
Thus the C++ program for implementation of Spanning Tree was created, executed and output
was verified successfully.
 EX. No. 10(A) Date: …………..
SHORTEST PATH ALGORITHMS (DIJKSTRA'S ALGORITHM)
AIM
To write a program in C++ to implement the Dijkstra's algorithm.

DESCRIPTION

1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest
path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this
set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as
INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
a) Pick a vertex u which is not there in sptSet and has minimum distance value.
b) Include u to sptSet.
c) Update distance value of all adjacent vertices of u. To update the distance values,
iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance
value of u (from source) and weight of edge u-v, is less than the distance value of v,
then update the distance value of v.

PROGRAM

#include <limits.h>
#include <stdio.h>
int minDistance(int dist[], bool sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
int printSolution(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++)
{ int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
 && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
int main()
{
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;
}

OUTPUT

Vertex Distance from Source

0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14

RESULT:
Thus the C++ program for implementation of Dijkstra's algorithm was created, executed and
output was verified successfully.
 EX. No. 10(B) Date: …………..
SHORTEST PATH ALGORITHMS (BELLMAN FORD ALGORITHM)
AIM
To write a program in C++ to implement the Bellman Ford Algorithm.

DESCRIPTION

1) This step initializes distances from source to all vertices as infinite and distance to source
itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src] where src
is source vertex.
2) This step calculates shortest distances. Do following |V|-1 times where |V| is the number of
vertices in given graph.
a) Do following for each edge u-v
If dist[v] > dist[u] + weight of edge uv, then update dist[v]
dist[v] = dist[u] + weight of edge uv
3) This step reports if there is a negative weight cycle in graph. Do following for each edge u-
If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight cycle”
The idea of step 3 is, step 2 guarantees shortest distances if graph doesn’t contain negative
weight cycle. If we iterate through all edges one more time and get a shorter path for any vertex,
then there is a negative weight cycle

PROGRAM

#include <bits/stdc++.h>
using namespace std;
void BellmanFord(int graph[][3], int V, int E,
int src)
{
int dis[V];
for (int i = 0; i < V; i++)
dis[i] = INT_MAX;
dis[src] = 0;
for (int i = 0; i < V - 1; i++)
{ for (int j = 0; j < E; j++) {
if (dis[graph[j][0]] != INT_MAX && dis[graph[j][0]] + graph[j][2] <
dis[graph[j][1]])
dis[graph[j][1]] =
dis[graph[j][0]] + graph[j][2];
}
}
for (int i = 0; i < E; i++)
{ int x = graph[i][0];
int y = graph[i][1];
int weight = graph[i][2];
if (dis[x] != INT_MAX &&
dis[x] + weight < dis[y])
cout << "Graph contains negative"
" weight cycle"
<< endl;
 }

cout << "Vertex Distance from Source" << endl;

for (int i = 0; i < V; i++)
cout << i << "\t\t" << dis[i] << endl;
}
int main()
{
int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
int graph[][3] = { { 0, 1, -1 }, { 0, 2, 4 },
{ 1, 2, 3 }, { 1, 3, 2 },
{ 1, 4, 2 }, { 3, 2, 5 },
{ 3, 1, 1 }, { 4, 3, -3 } };
BellmanFord(graph, V, E, 0);
return 0;
}

OUTPUT:
Vertex Distance from Source
0 0
1 -1
2 2
3 -2
4 1

RESULT:
Thus the C++ program for implementation of Bellman Ford Algorithm was created, executed
and output was verified successfully.
 EX. No. 11 Date: …………..
IMPLEMENTATION OF MATRIX CHAIN MULTIPLICATION
AIM
To write a program in C++ to implement the matrix chain multiplication.

DESCRIPTION

1. m[1,1] tells us about the operation of multiplying matrix A with itself which will be 0.
So fill all the m[i,i] as 0.
2. m[1,2] We are multiplying two matrices A and B. Operations will be 5*4*6=120.
3. m[2,3] We are multiplying B and C now. Operations will be 4*6*2=48
4. m[3,4] can be also filled in the same way.

PROGRAM

#include<bits/stdc++.h>
using namespace std;
int MatrixChainOrder(int p[], int n)
{
int m[n][n];
int i, j, k, L, q;

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

m[i][i] = 0;
for (L=2; L<n; L++) //filling half table only
{
for (i=1; i<n-L+1; i++)
{
j = i+L-1;
m[i][j] = INT_MAX;
for (k=i; k<=j-1; k++)
{
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n-1];
}
int main()
{
int arr[] = {5,4,6,2,7};
int size = 5;
cout<<MatrixChainOrder(arr,size)<<" operations";

}
OUTPUT:

158 operations

RESULT:
Thus the C++ program for implementation of matrix chain multiplication was created, executed
and output was verified successfully.
 EX. No. 12(A) Date: …………..
ACTIVITY SELECTION IMPLEMENTATION
AIM
To write a program in C++ to implement the activity selection.

DESCRIPTION

1) Sort the activities according to their finishing time

2) Select the first activity from the sorted array and print it.
3) Do the following for the remaining activities in the sorted array.
a) If the start time of this activity is greater than or equal to the finish time of the
previously selected activity then select this activity and print it.

PROGRAM

#include <bits/stdc++.h>
using namespace std;
void printMaxActivities(int s[], int f[], int n)
{
int i, j;

cout <<"Following activities are selected "<< endl;

i = 0;
cout <<" "<< i;
for (j = 1; j < n; j++)
{
if (s[j] >= f[i])
{
cout <<" " << j;
i = j;
}
}
}
int main()
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = sizeof(s)/sizeof(s[0]);
printMaxActivities(s, f, n);
return 0;
}

OUTPUT
Following activities are selected n0 1 3 4

RESULT:
Thus the C++ program for implementation of Activity Selection was created, executed and
output was verified successfully.
 EX. No. 12(B) Date: …………..
HUFFMAN CODING IMPLEMENTATION
AIM
To write a program in C++ to implement the Huffman Coding.

DESCRIPTION

1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min
Heap is used as a priority queue. The value of frequency field is used to compare two
nodes in min heap. Initially, the least frequent character is at root)
2. Extract two nodes with the minimum frequency from the min heap.

3. Create a new internal node with a frequency equal to the sum of the two nodes
frequencies. Make the first extracted node as its left child and the other extracted node
as its right child. Add this node to the min heap.
4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the
root node and the tree is complete

PROGRAM

#include <iostream>
#include <cstdlib>
using namespace std;
#define MAX_TREE_HT 100
struct MinHeapNode {
char data;
unsigned freq;
struct MinHeapNode *left, *right;
};
struct MinHeap

{ unsigned size;

unsigned capacity;

struct MinHeapNode** array;

};

struct MinHeapNode* newNode(char data, unsigned freq)

{
struct MinHeapNode* temp
= (struct MinHeapNode*)malloc
(sizeof(struct MinHeapNode));

temp->left = temp->right = NULL;

temp->data = data;
temp->freq = freq;
 return temp;
}

struct MinHeap* createMinHeap(unsigned capacity)

struct MinHeap* minHeap

= (struct MinHeap*)malloc(sizeof(struct MinHeap));

minHeap->size = 0;

minHeap->capacity = capacity;

minHeap->array
= (struct MinHeapNode**)malloc(minHeap->
capacity * sizeof(struct MinHeapNode*));
return minHeap;
}

void swapMinHeapNode(struct MinHeapNode** a,

struct MinHeapNode** b)

struct MinHeapNode* t = *a;

*a = *b;
*b = t;
}

void minHeapify(struct MinHeap* minHeap, int idx)

int smallest = idx;

int left = 2 * idx + 1;
int right = 2 * idx + 2;

if (left < minHeap->size && minHeap->array[left]->

freq < minHeap->array[smallest]->freq)
smallest = left;

if (right < minHeap->size && minHeap->array[right]->

freq < minHeap->array[smallest]->freq)
smallest = right;

if (smallest != idx)
{ swapMinHeapNode(&minHeap-
>array[smallest],
&minHeap->array[idx]);
minHeapify(minHeap, smallest);
 }
}

int isSizeOne(struct MinHeap* minHeap)

{

return (minHeap->size == 1);

}

struct MinHeapNode* extractMin(struct MinHeap* minHeap)

struct MinHeapNode* temp = minHeap->array[0];

minHeap->array[0]
= minHeap->array[minHeap->size - 1];

--minHeap->size;
minHeapify(minHeap, 0);

return temp;
}

void insertMinHeap(struct MinHeap* minHeap,

struct MinHeapNode* minHeapNode)

++minHeap->size;
int i = minHeap->size - 1;

while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {

minHeap->array[i] = minHeap->array[(i - 1) / 2];

i = (i - 1) / 2;
}

minHeap->array[i] = minHeapNode;
}
void buildMinHeap(struct MinHeap* minHeap)

int n = minHeap->size - 1;
int i;

for (i = (n - 1) / 2; i >= 0; --i)

minHeapify(minHeap, i);
}
void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
cout<< arr[i];

cout<<"\n";
}

int isLeaf(struct MinHeapNode* root)

return !(root->left) && !(root->right);

}

struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size)

struct MinHeap* minHeap = createMinHeap(size);

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

minHeap->array[i] = newNode(data[i], freq[i]);

minHeap->size = size;
buildMinHeap(minHeap);

return minHeap;
}

struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size)

{
struct MinHeapNode *left, *right, *top;
struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
while (!isSizeOne(minHeap)) {

left = extractMin(minHeap);
right = extractMin(minHeap);

top = newNode('$', left->freq + right->freq);

top->left = left;
top->right = right;

insertMinHeap(minHeap, top);
}
 return extractMin(minHeap);
}

void printCodes(struct MinHeapNode* root, int arr[], int top)

if (root->left) {

arr[top] = 0;
printCodes(root->left, arr, top + 1);
}

if (root->right) {

arr[top] = 1;
printCodes(root->right, arr, top + 1);
}

if (isLeaf(root)) {

cout<< root->data <<": ";

printArr(arr, top);
}
}

void HuffmanCodes(char data[], int freq[], int size)

struct MinHeapNode* root

= buildHuffmanTree(data, freq, size);

int arr[MAX_TREE_HT], top = 0;

printCodes(root, arr, top);

}

int main()
{

char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };

int freq[] = { 5, 9, 12, 13, 16, 45 };

int size = sizeof(arr) / sizeof(arr[0]);

HuffmanCodes(arr, freq, size);

return 0;
}
OUTPUT:

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

RESULT:
Thus the C++ program for implementation of Huffman Coding was created, executed and
output was verified successfully.