PET ENGINEERING COLLEGE

VALLIOOR – 627 117

DEPARTMENT OF MASTER OF COMPUTER APPLICATION

ADVANCED DATA STRUCTURE AND ALGORITHMS

LABORATORY MC4111
 PET ENGINEERING COLLEGE
VALLIOOR – 627 117

DEPARTMENT OF MASTER OF COMPUTER APPLICATION

ADVANCED DATA STRUCTURE AND ALGORITHM

LABORATORY MC4111

Name :

Reg.No. :

Year& Sem. :
 PET ENGINEERING COLLEGE
VALLIOOR–627 117
DEPARTMENT OF MASTER OF COMPUTER APPLICATION

CERTIFICATE

Certified that this is the bonafide record of work done by

Ms./Mr./Mrs. _____________________________ of first Semester of this college in
ADVANCED DATA STRUCTURE AND ALGORITHM LABORATORY-
MC4112 during the academic year 2024 – 2025 in partial fulfillment of the
requirement of MCA degree of the Anna University, Chennai .

Staff in-charge Head of the Department

University Reg.No :

University Examination held on :

Internal Examiner External Examiner

Program:
#include <iostream>
using namespace std;
int binarySearchRecursive(int arr[], int left, int right, int target) {
if (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] > target)
return binarySearchRecursive(arr, left, mid - 1, target);
return binarySearchRecursive(arr, mid + 1, right, target);
}
return -1;
}
int binarySearchNonRecursive(int arr[], int size, int target) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return -1; // Target not found
}
int main() {
int arr[] = {2, 4, 6, 8, 10, 12, 14};
int size = sizeof(arr) / sizeof(arr[0]);
int target;
cout << "Enter the element to search: ";
cin >> target;
int resultRecursive = binarySearchRecursive(arr, 0, size - 1, target);
if (resultRecursive != -1)
cout << "Element found at index (Recursive): " << resultRecursive << endl;
else
cout << "Element not found (Recursive)" << endl;

int resultNonRecursive = binarySearchNonRecursive(arr, size, target);

if (resultNonRecursive != -1)
cout << "Element found at index (Non-Recursive): " << resultNonRecursive << endl;
else
cout << "Element not found (Non-Recursive)" << endl;
return 0;
}

Output:
Enter the element to search: 10
Element found at index (Recursive): 4
Element found at index (Non-Recursive): 4
--------------------------------

Enter the element to search: 7

Element not found (Recursive)
Element not found (Non-Recursive)
--------------------------------
Program:
#include <iostream>
using namespace std;
void merge(int a[], int l, int m, int r) {
int b[r - l + 1], i = l, j = m + 1, k = 0;
while (i <= m && j <= r) b[k++] = (a[i] < a[j]) ? a[i++] : a[j++];
while (i <= m) b[k++] = a[i++];
while (j <= r) b[k++] = a[j++];
for (i = l, k = 0; i <= r; i++) a[i] = b[k++];
}
void mergeSort(int a[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
merge(a, l, m, r);
}
}
int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
int a[n];
cout << "Enter the elements one by one : ";
for (int i = 0; i < n; i++) cin >> a[i];
mergeSort(a, 0, n - 1);
cout << "Sorted: ";
for (int i = 0; i < n; i++) cout << a[i] << " ";
}

Output:

Enter number of elements: 5

Enter elements: 3 4 1 27 0
Sorted: 0 1 3 4 27
--------------------------------
 Program:
#include <iostream>
#include <vector>
using namespace std;
void heapify(vector<int>& arr, int n, int i)
{
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
void heapSort(vector<int>& arr)
{
for (int i = arr.size() / 2 - 1; i >= 0; i--) heapify(arr, arr.size(), i);
for (int i = arr.size() - 1; i > 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); }
}
int main()
{
int n;
cout << "Enter number of elements: ";
cin >> n;
vector<int> arr(n);
cout << "Enter elements: ";
for (int i = 0; i < n; i++) cin >> arr[i];
heapSort(arr);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}

Output:
Enter number of elements: 6
Enter elements: 1 3 0 2 8 6
Sorted array: 0 1 2 3 6 8
--------------------------------
Program:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = NULL;
right = NULL;
}
};
void inOrderTraversal(Node* root) {
if (root == NULL) {
return;
}
inOrderTraversal(root->left);
cout << root->data << " ";
inOrderTraversal(root->right);
}
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "In-order Traversal: ";
inOrderTraversal(root);
cout << endl;
return 0;
}

Output:
In-order Traversal: 4 2 5 1 3
--------------------------------
Program:
#include <iostream>
#include <vector>
using namespace std;
bool dfs(int current, int target, vector<vector<int> >& adj, vector<bool>& visited)
{
if (current == target)
return true;
}
visited[current] = true;
for (int i = 0; i < adj[current].size(); i++)
{
int neighbor = adj[current][i];
if (!visited[neighbor])
{
if (dfs(neighbor, target, adj, visited))
return true;
}
}
return false;
}
int main()
{
int vertices, edges;
cout << "Enter the number of vertices: ";
cin >> vertices;
cout << "Enter the number of edges: ";
cin >> edges;
vector<vector<int> > adj(vertices);
cout << "Enter the edges (from to):" << endl;
for (int i = 0; i < edges; i++) {
int from, to;
cin >> from >> to;
adj[from].push_back(to);
adj[to].push_back(from);
}
int start, end;
 cout << "Enter the start and end vertices: ";
cin >> start >> end;
vector<bool> visited(vertices, false);
if (dfs(start, end, adj, visited))
{
cout << "There is a path from " << start << " to " << end << "." << endl;
}
else
{
cout << "No path exists from " << start << " to " << end << "." << endl;
}
return 0;
}

Output:
Enter the number of vertices: 5
Enter the number of edges: 4
Enter the edges (from to):
01
02
23
34
Enter the start and end vertices: 0 4
There is a path from 0 to 4.
--------------------------------

Enter the number of vertices: 5

Enter the number of edges: 3
Enter the edges (from to):
01
12
34
Enter the start and end vertices: 0 4
No path exists from 0 to 4.
--------------------------------
Program:
#include <iostream>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int dfs(TreeNode* node, int prev1, int prev2)
{
if (!node) return 0;
int count = (node->val == prev1 + prev2) ? 1 : 0;
return count + dfs(node->left, prev1 + prev2, prev1) + dfs(node->right, prev1 + prev2,
prev1);
}
int countFibonacciPaths(TreeNode* root)
{
if (!root) return 0;
return dfs(root, 0, root->val) + countFibonacciPaths(root->left) + countFibonacciPaths
(root->right);
}
int main()
{
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(3);
root->right = new TreeNode(8);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(4);
root->right->left = new TreeNode(7);
root->right->right = new TreeNode(10);
cout << "Number of Fibonacci paths: " << countFibonacciPaths(root) << endl;
return 0;
}
Output:
Number of Fibonacci paths: 8
--------------------------------
Program:
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
Node(int value) : data(value), left(NULL), right(NULL) {}
};
void preorderTraversal(Node* root)
{
if (root == NULL) return;
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main()
{
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "Preorder Traversal: ";
preorderTraversal(root);
cout << endl;
return 0;
}

Output:
Preorder Traversal: 1 2 4 5 3
--------------------------------
Program:

#include <iostream>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i <= n / 2; i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int limit;
cout<<"Enter the number:";
cin >> limit;
for (int i = 2; i <= limit; i++) {
if (isPrime(i))
cout << i << " ";
cout
}
return 0;
}

Output:

Enter the number: 15

Prime numbers: 2 3 5 7 11 13
--------------------------------
Program:

#include <iostream>
using namespace std;
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
int main() {
int a, b;
cout<<"Enter the number a & b :";
cin >> a >> b;
cout << "GCD of given Number is "<<" "<<gcd(a, b);
return 0;
}
Output:
Enter the number a & b: 45 30
GCD of given Number is 15
--------------------------------
Program:
#include <iostream>
#include <vector>
using namespace std;
void DFS(int node, vector<int> adj[], bool visited[])
{
visited[node] = true;
cout << node << " ";
for (int i = 0; i < adj[node].size(); i++)
{
it adjacent = adj[node][i];
if (!visited[adjacent])
{
DFS(adjacent, adj, visited);
}}}
int main()
{
int vertices = 5;
vector<int> adj[vertices];
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(0);
adj[1].push_back(3);
adj[1].push_back(4);
adj[2].push_back(0);
adj[3].push_back(1);
adj[4].push_back(1);
bool visited[vertices] = {false};
cout << "DFS Traversal: ";
DFS(0, adj, visited);
return 0;
}

Output:

DFS Traversal: 0 1 3 4 2
--------------------------------
Program:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge
{
int u, v, w;
};
bool cmp(Edge a, Edge b)
{
return a.w < b.w;
}
int find(int x, vector<int>& parent)
{
if (parent[x] != x)
parent[x] = find(parent[x], parent);
return parent[x];
}
void kruskal(int n, vector<Edge>& edges)
{
sort(edges.begin(), edges.end(), cmp);
vector<int> parent(n);
for (int i = 0; i < n; ++i)
parent[i] = i;
int mstWeight = 0;
for (size_t i = 0; i < edges.size(); ++i)
{
Edge e = edges[i];
int uRoot = find(e.u, parent);
int vRoot = find(e.v, parent);
if (uRoot != vRoot)
{
mstWeight += e.w;
parent[uRoot] = vRoot;
cout << e.u << " - " << e.v << " (" << e.w << ")\n";
}
 }

cout << "Total weight: " << mstWeight << endl;

}
int main()
{
int n = 4, m = 5;
vector<Edge> edges;
edges.push_back((Edge){0, 1, 10});
edges.push_back((Edge){0, 2, 6});
edges.push_back((Edge){0, 3, 5});
edges.push_back((Edge){1, 3, 15});
edges.push_back((Edge){2, 3, 4});
kruskal(n, edges);
return 0;
}

Output:

2 - 3 (4)
0 - 3 (5)
0 - 1 (10)
Total weight: 19
-------------------------------
Program:
#include <iostream>
#include <vector>
#include <climits>
#include <sstream>
using namespace std;
string toStr(int num)
{
stringstream ss;
ss << num;
return ss.str();
}
void bellmanFord(int v, int e, vector<vector<int> >& edges, int src)
{
vector<int> dist(v, INT_MAX);
dist[src] = 0;
for (int i = 0; i < v - 1; ++i)
{
for (int j = 0; j < e; ++j)
{
int u = edges[j][0];
int v = edges[j][1];
int w = edges[j][2];
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
}
}
}
for (int j = 0; j < e; ++j)
{
int u = edges[j][0];
int v = edges[j][1];
int w = edges[j][2];
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
{
cout << "Negative cycle detected\n";
 return;
}
}
for (int i = 0; i < v; ++i)
{
cout << "Distance to " << i << ": " << (dist[i] == INT_MAX ? "INF" : toStr(dist[i])) << "\n";
}
}
int main()
{
int v, e, src;
cout << "Enter vertices, edges: ";
cin >> v >> e;
vector<vector<int> > edges(e, vector<int>(3));
cout << "Enter edges (u v w):\n";
for (int i = 0; i < e; ++i)
cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
cout << "Enter source vertex: ";
cin >> src;
bellmanFord(v, e, edges, src);
return 0;
}

Output:

Enter vertices, edges: 3 3

Enter edges (u v w):
011
012
1 2 -3
Enter source vertex: 0
Distance to 0: 0
Distance to 1: 1
Distance to 2: -2
Program:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int arr[] = {10, 20, 30};
std::vector<int> heap(arr, arr + sizeof(arr) / sizeof(arr[0]));
std::make_heap(heap.begin(), heap.end());
std::cout << "Initial heap: ";
for (std::vector<int>::iterator it = heap.begin(); it != heap.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
heap.push_back(25);
std::push_heap(heap.begin(), heap.end());
std::cout << "Heap after push_heap: ";
for (std::vector<int>::iterator it = heap.begin(); it != heap.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
std::pop_heap(heap.begin(), heap.end());
int largest = heap.back();
heap.pop_back();
std::cout << "Heap after pop_heap: ";
for (std::vector<int>::iterator it = heap.begin(); it != heap.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
std::cout << "Popped element: " << largest << std::endl;
return 0;
}
Output:
Initial heap: 30 20 10
Heap after push_heap: 30 25 10 20
Heap after pop_heap: 25 20 10
Popped element: 30
--------------------------------
Program:
#include <iostream>
using namespace std;
const int INF = 9999;
const int MAX = 10;
void dijkstra(int G[MAX][MAX], int n, int startnode)
{
int distance[n], pred[n];
bool visited[n] = {false};
fill(distance, distance + n, INF);
distance[startnode] = 0;
for (int count = 0; count < n - 1; count++)
{
int mindistance = INF, nextnode = -1;
for (int i = 0; i < n; i++)
{
if (!visited[i] && distance[i] < mindistance)
{
mindistance = distance[i];
nextnode = i;
}
}
visited[nextnode] = true;
for (int i = 0; i < n; i++) {
if (!visited[i] && G[nextnode][i] != INF && distance[nextnode] + G[nextnode][i] <
distance[i]) {
distance[i] = distance[nextnode] + G[nextnode][i];
pred[i] = nextnode;
}
}
}
cout << "Shortest distances from source " << startnode << ":\n";
for (int i = 0; i < n; i++) {
if (i != startnode) {
cout << "Distance of node " << i << " = " << distance[i] << "\nPath = ";
for (int j = i; j != startnode; j = pred[j])
cout << j << "<-";
cout << startnode << endl;
 }
}
}
int main() {
int n, G[MAX][MAX], startnode;
cout << "Enter number of vertices: ";
cin >> n;
cout << "Enter the adjacency matrix:\n";
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> G[i][j];
if (G[i][j] == 0) G[i][j] = INF;
}
cout << "Enter the starting node: ";
cin >> startnode;
dijkstra(G, n, startnode);
return 0;
}

Output:
Enter number of vertices: 3
Enter the adjacency matrix:
123
456
789
Enter the starting node: 1
Shortest distances from source 1:
Distance of node 0 = 4
Path = 0<-1
Distance of node 2 = 6
Path = 2<-1
--------------------------------
Program:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node
{
char item;
int freq;
Node* left, *right;
};
struct Compare
{
bool operator()(Node* a, Node* b)
{
return a->freq > b->freq;
}
};
void printHuffmanCodes(Node* root, string str)
{
if (root == NULL) return;
if (root->left == NULL && root->right == NULL)
{
cout << root->item << ": " << str << endl;
return;
}
printHuffmanCodes(root->left, str + "0");
printHuffmanCodes(root->right, str + "1");
}

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

{
priority_queue<Node*, vector<Node*>, Compare> pq;
for (int i = 0; i < size; i++)
{
Node* newNode = new Node();
newNode->item = item[i];
newNode->freq = freq[i];
 newNode->left = newNode->right = NULL;
pq.push(newNode);
}
while (pq.size() != 1)
{
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
Node* newNode = new Node();
newNode->item = '\0';
newNode->freq = left->freq + right->freq;
newNode->left = left;
newNode->right = right;
pq.push(newNode);
}
printHuffmanCodes(pq.top(), "");
}
int main()
{
char item[] = {'A', 'B', 'C', 'D'};
int freq[] = {5, 1, 6, 3};
int size = sizeof(item) / sizeof(item[0]);
cout << "Character | Huffman code" << endl;
HuffmanCodes(item, freq, size);
return 0;
}
Output:
Character | Huffman code
C: 0
B: 100
D: 101
A: 11
--------------------------------
Program:

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int LCS(string s1, string s2) {
int m = s1.length(), n = s2.length();
vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0)); '
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
int main() {
string s1 = "stone", s2 = "longest";
cout << "Length of LCS: " << LCS(s1, s2) << endl;
return 0;
}

Output:

Length of LCS: 3
--------------------------------
Program:
#include <iostream>
using namespace std;
void activitySelection(int start[], int finish[], int n) {
int i = 0;
cout << "Selected activities: " << i << " ";
for (int j = 1; j < n; j++) {
if (start[j] >= finish[i]) {
cout << j << " ";
i = j;
}
}
}
int main() {
int start[] = {1, 3, 0, 5, 8, 5};
int finish[] = {2, 4, 6, 7, 9, 9};
int n = 6;
activitySelection(start, finish, n);
return 0;
}
Output:

Selected activities: 0 1 3 4
--------------------------------