GALGOTIAS COLLEGE OF ENGINEERING & TECHNOLOGY

Data Structures & Analysis Of Algorithms Lab

Subject Code: BMC252
Semester: II

Session: 2024-25

Submitted To: Submitted By:

Mr. Shahid Ahmad Wani Anurag Kumar Jha
MCA Department Roll No: 2400970140036

Department of Computer Applications

Knowledge Park I, Greater Noida, Uttar Pradesh 201310
INDEX
S.No. Name of the Program Date of Date of Sign
Implementation Submission
1. To implement addition and multiplication
of two 2D arrays.

2. To transpose a 2D array.

3. To implement stack using array

4. To implement queue using array.

5. To implement circular queue using array.

6. To implement stack using linked list.

7. To implement queue using linked list.

8. To implement BFS using linked list.

9. To implement DFS using linked list.

10. To implement Linear Search.

11. To implement Binary Search.

12. To implement Bubble Sorting.

13. To implement Selection Sorting.

14. To implement Insertion Sorting.

15. To implement Merge Sorting.

16. To implement Heap Sorting.

17. To implement Matrix Multiplication by

Strassen’s algorithm

18. Find Minimum Spanning Tree using

Kruskal’s Algorithm
EXPERIMENT-1
Aim: - To implement addition and multiplication of two 2D arrays.
Code:
#include <iostream>
using namespace std;
const int MAX = 10;
void inputMatrix(int matrix[MAX][MAX], int rows, int cols, string name) {
cout << "Enter elements of " << name << " (" << rows << "x" << cols << "):\n";
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
cin >> matrix[i][j];
}
void displayMatrix(int matrix[MAX][MAX], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++)
cout << matrix[i][j] << " ";
cout << endl;
}
}
void addMatrices(int A[MAX][MAX], int B[MAX][MAX], int result[MAX][MAX], int rows, int cols) {
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
result[i][j] = A[i][j] + B[i][j];
}
void multiplyMatrices(int A[MAX][MAX], int B[MAX][MAX], int result[MAX][MAX], int r1, int c1, int c2) {
// Initialize result matrix with 0
for (int i = 0; i < r1; i++)
for (int j = 0; j < c2; j++)
result[i][j] = 0;
for (int i = 0; i < r1; i++)
for (int j = 0; j < c2; j++)
for (int k = 0; k < c1; k++)
result[i][j] += A[i][k] * B[k][j];
}
int main() {
int A[MAX][MAX], B[MAX][MAX], result[MAX][MAX];
int r1, c1, r2, c2;
// Input dimensions
cout << "Enter rows and columns of matrix A: ";
cin >> r1 >> c1;
cout << "Enter rows and columns of matrix B: ";
cin >> r2 >> c2;
inputMatrix(A, r1, c1, "Matrix A");
inputMatrix(B, r2, c2, "Matrix B");
// Matrix Addition
if (r1 == r2 && c1 == c2) {
addMatrices(A, B, result, r1, c1);
cout << "\nAddition of the matrices:\n";
displayMatrix(result, r1, c1);
} else {
cout << "\nAddition not possible: dimensions do not match.\n";
}
// Matrix Multiplication
if (c1 == r2) {
multiplyMatrices(A, B, result, r1, c1, c2);
cout << "\nMultiplication of the matrices:\n";
displayMatrix(result, r1, c2);
} else {
cout << "\nMultiplication not possible: columns of A != rows of B.\n";
}
return 0;
}
Output: -
EXPERIMENT- 2
Aim: - To transpose a 2D array.
Code:
#include <iostream>
using namespace std;
const int MAX = 10;
void inputMatrix(int matrix[MAX][MAX], int rows, int cols) {
cout << "Enter elements of the matrix (" << rows << "x" << cols << "):\n";
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
cin >> matrix[i][j];
}
void displayMatrix(int matrix[MAX][MAX], int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++)
cout << matrix[i][j] << " ";
cout << endl;
}
}
void transposeMatrix(int matrix[MAX][MAX], int transposed[MAX][MAX], int rows, int cols) {
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
transposed[j][i] = matrix[i][j];
}
int main() {
int matrix[MAX][MAX], transposed[MAX][MAX];
int rows, cols;
cout << "Enter number of rows and columns: ";
cin >> rows >> cols;
inputMatrix(matrix, rows, cols);
transposeMatrix(matrix, transposed, rows, cols);
cout << "\nOriginal Matrix:\n";
displayMatrix(matrix, rows, cols);
cout << "\nTransposed Matrix:\n";
displayMatrix(transposed, cols, rows);
return 0;
}

Output: -
EXPERIMENT - 3
Aim: - To implement stack using array.
Code:
#include <iostream>
using namespace std;
#define MAX 100
class Stack {
int arr[MAX];
int top;
public:
Stack() { top = -1; }
bool isFull() {
return top == MAX - 1;
}
bool isEmpty() {
return top == -1;
}
void push(int value) {
if (isFull()) {
cout << "Stack Overflow! Cannot push " << value << endl;
return;
}
arr[++top] = value;
cout << value << " pushed to stack.\n";
}
void pop() {
if (isEmpty()) {
cout << "Stack Underflow! Cannot pop.\n";
return;
}
cout << arr[top--] << " popped from stack.\n";
}
void peek() {
if (isEmpty()) {
cout << "Stack is empty.\n";
return;
}
cout << "Top element is: " << arr[top] << endl;
}
void display() {
if (isEmpty()) {
cout << "Stack is empty.\n";
return;
}
cout << "Stack elements:\n";
for (int i = top; i >= 0; i--)
cout << arr[i] << " ";
cout << endl;
}
};

int main() {

Stack stack;
int choice, value;

do {
cout << "\n--- Stack Menu ---\n";
cout << "1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter value to push: ";
cin >> value;
stack.push(value);
break;
case 2:
stack.pop();
break;
case 3:
stack.peek();
break;
case 4:
stack.display();
break;
case 5:
cout << "Exiting...\n";
break;
default:
cout << "Invalid choice.\n";
}
} while (choice != 5);
return 0;
}
Output:
EXPERIMENT - 4
Aim: - To implement queue using array.
Code:
#include <iostream>
using namespace std;
#define MAX 100

class Queue {
int arr[MAX];
int front, rear;

public:
Queue() {
front = -1;
rear = -1;
}

bool isEmpty() {
return front == -1 || front > rear;
}

bool isFull() {
return rear == MAX - 1;
}

void enqueue(int value) {

if (isFull()) {
cout << "Queue Overflow! Cannot enqueue " << value << endl;
return;
}
if (isEmpty()) {
front = 0;
}
arr[++rear] = value;
cout << value << " enqueued to queue.\n";
}

void dequeue() {
if (isEmpty()) {
cout << "Queue Underflow! Cannot dequeue.\n";
return;
}
cout << arr[front++] << " dequeued from queue.\n";
}
void peek() {
if (isEmpty()) {
cout << "Queue is empty.\n";
return;
}
cout << "Front element is: " << arr[front] << endl;
}

void display() {
if (isEmpty()) {
cout << "Queue is empty.\n";
return;
}
cout << "Queue elements: ";
for (int i = front; i <= rear; i++)
cout << arr[i] << " ";
cout << endl;
}
};

int main() {
Queue queue;
int choice, value;

do {
cout << "\n--- Queue Menu ---\n";
cout << "1. Enqueue\n2. Dequeue\n3. Peek\n4. Display\n5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to enqueue: ";
cin >> value;
queue.enqueue(value);
break;
case 2:
queue.dequeue();
break;
case 3:
queue.peek();
break;
case 4:
queue.display();
break;
case 5:
cout << "Exiting...\n";
break;
default:
cout << "Invalid choice.\n";
}
} while (choice != 5);

return 0;
}
Output: -
EXPERIMENT -5
Aim: - To implement circular queue using array.
Code:
#include <iostream>
using namespace std;
#define SIZE 5
class CircularQueue {
int arr[SIZE];
int front, rear;

public:
CircularQueue() {
front = -1;
rear = -1;
}

bool isFull() {
return (front == (rear + 1) % SIZE);
}

bool isEmpty() {
return (front == -1);
}

void enqueue(int value) {

if (isFull()) {
cout << "Queue Overflow! Cannot enqueue " << value << endl;
return;
}
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % SIZE;
}
arr[rear] = value;
cout << value << " enqueued.\n";
}

void dequeue() {
if (isEmpty()) {
cout << "Queue Underflow! Cannot dequeue.\n";
return;
}
cout << arr[front] << " dequeued.\n";

if (front == rear) {
// Only one element was present
front = rear = -1;
} else {
front = (front + 1) % SIZE;
}
}

void peek() {
if (isEmpty()) {
cout << "Queue is empty.\n";
return;
}
cout << "Front element: " << arr[front] << endl;
}

void display() {
if (isEmpty()) {
cout << "Queue is empty.\n";
return;
}
cout << "Queue elements: ";
int i = front;
while (true) {
cout << arr[i] << " ";
if (i == rear)
break;
i = (i + 1) % SIZE;
}
cout << endl;
}
};

int main() {
CircularQueue cq;
int choice, value;

do {
cout << "\n--- Circular Queue Menu ---\n";
cout << "1. Enqueue\n2. Dequeue\n3. Peek\n4. Display\n5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to enqueue: ";
cin >> value;
cq.enqueue(value);
break;
case 2:
cq.dequeue();
break;
case 3:
cq.peek();
break;
case 4:
cq.display();
break;
case 5:
cout << "Exi ng...\n";
break;
default:
cout << "Invalid choice.\n";
}
} while (choice != 5);
return 0;
}
Output: -
EXPERIMENT - 6
Aim : - To implement stack using linked list.
Code
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};

class Stack {
Node* top;
public:
Stack() {
top = nullptr;
}
bool isEmpty() {
return top == nullptr;
}

void push(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->next = top;
top = newNode;
cout << value << " pushed to stack.\n";
}

void pop() {
if (isEmpty()) {
cout << "Stack Underflow! Cannot pop.\n";
return;
}
Node* temp = top;
cout << temp->data << " popped from stack.\n";
top = top->next;
delete temp;
}

void peek() {
if (isEmpty()) {
cout << "Stack is empty.\n";
return;
}
cout << "Top element is: " << top->data << endl;
}

void display() {
if (isEmpty()) {
cout << "Stack is empty.\n";
return;
}

Node* temp = top;

cout << "Stack elements:\n";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

~Stack() {
while (!isEmpty()) {
pop();
}
}
};

int main() {
Stack stack;
int choice, value;
do {

cout << "\n--- Stack Menu ---\n";

cout << "1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to push: ";
cin >> value;
stack.push(value);
break;
case 2:
stack.pop();
break;
case 3:
stack.peek();
break;
case 4:
stack.display();
break;
case 5:
cout << "Exi ng...\n";
break;
default:
cout << "Invalid choice.\n";
}
} while (choice != 5);

return 0;
}

OUTPUT:-
EXPERIMENT - 7
Aim:- To implement queue using linked list.
Code:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};

class Queue {
Node* front;
Node* rear;

public:
Queue() {
front = rear = nullptr;
}

bool isEmpty() {
return front == nullptr;
}

void enqueue(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;

if (rear == nullptr) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}

cout << value << " enqueued to queue.\n";

}

void dequeue() {
if (isEmpty()) {
cout << "Queue Underflow! Cannot dequeue.\n";
return;
}
Node* temp = front;
cout << temp->data << " dequeued from queue.\n";
front = front->next;

if (front == nullptr) {
rear = nullptr;
}

delete temp;
}

void peek() {
if (isEmpty()) {
cout << "Queue is empty.\n";
return;
}
cout << "Front element: " << front->data << endl;
}

void display() {
if (isEmpty()) {
cout << "Queue is empty.\n";
return;
}

Node* temp = front;

cout << "Queue elements: ";
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

~Queue() {
while (!isEmpty()) {
dequeue();
}
}
};

int main() {

Queue q;
int choice, value;

do {
cout << "\n--- Queue Menu ---\n";
cout << "1. Enqueue\n2. Dequeue\n3. Peek\n4. Display\n5. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to enqueue: ";
cin >> value;
q.enqueue(value);
break;
case 2:
q.dequeue();
break;
case 3:
q.peek();
break;
case 4:
q.display();
break;
case 5:
cout << "Exi ng...\n";
break;
default:
cout << "Invalid choice.\n";
}
} while (choice != 5);

return 0;
}

OUTPUT:
EXPERIMENT – 8
Aim :To implement BFS using linked list.
Code:
#include <iostream>
#include <list>
using namespace std;

class Graph {
int V;
list<int> *adj;

public:
Graph(int V);
void addEdge(int v, int w);
void BFS(int s);
};

Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}

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

adj[v].push_back(w);
}

void Graph::BFS(int s) {
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

list<int> queue;
visited[s] = true;
queue.push_back(s);

while (!queue.empty()) {
s = queue.front();
cout << s << " ";
queue.pop_front();

for (auto adjacent : adj[s]) {

if (!visited[adjacent]) {
visited[adjacent] = true;
queue.push_back(adjacent);
}
}
}

delete[] visited;
}

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 << "Breadth First Traversal star ng from vertex 2:\n";

g.BFS(2);

return 0;
}

OUTPUT:
EXPERIMENT – 9
Aim :To implement DFS using linked list.
Code:
#include <iostream>
#include <list>
using namespace std;

class Graph {
int V;
list<int> *adj;

public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int v);

private:
void DFSU l(int v, bool visited[]);
};

Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}

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

adj[v].push_back(w);
}

void Graph::DFSU l(int v, bool visited[]) {

visited[v] = true;
cout << v << " ";

for (auto adjacent : adj[v]) {

if (!visited[adjacent]) {
DFSU l(adjacent, visited);
}
}
}

void Graph::DFS(int v) {
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

DFSU l(v, visited);

delete[] visited;
}

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 << "Depth First Traversal star ng from vertex 2:\n";

g.DFS(2);

return 0;
}

OUTPUT:
EXPERIMENT – 10
Aim : To implement linear search.
Code:
#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int key) {

for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i;
}
return -1;
}

int main() {
int n, key;

cout << "Enter number of elements: ";

cin >> n;

int arr[n];
cout << "Enter " << n << " elements:\n";
for (int i = 0; i < n; i++)
cin >> arr[i];

cout << "Enter element to search: ";

cin >> key;

int result = linearSearch(arr, n, key);

if (result != -1)
cout << "Element found at index " << result << ".\n";
else
cout << "Element not found in the array.\n";

return 0;
}
OUTPUT:
EXPERIMENT – 11
Aim : To implement binary search.
Code:
#include <iostream>
using namespace std;

int binarySearch(int arr[], int size, int key) {

int low = 0, high = size - 1;

while (low <= high) {

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

// Check if key is present at mid

if (arr[mid] == key)
return mid;

// If key greater, ignore le half

else if (arr[mid] < key)
low = mid + 1;

else
high = mid - 1;
}

// Key was not present

return -1;
}

int main() {

int arr[] = {2, 4, 10, 15, 23, 38, 56, 72, 91};
int size = sizeof(arr) / sizeof(arr[0]);
int key;

cout << "Enter the number to search: ";

cin >> key;

int result = binarySearch(arr, size, key);

if (result != -1)
cout << "Element found at index: " << result << endl;
else
cout << "Element not found in the array." << endl;
return 0;
}
OUTPUT:
EXPERIMENT – 12
Aim : To implement Bubble Sorting.
Code:
#include <iostream>
using namespace std;

void bubbleSort(int arr[], int size) {

for (int i = 0; i < size - 1; i++) {
// Last i elements are already sorted
for (int j = 0; j < size - i - 1; j++) {
// Swap if the current element is greater than the next
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

void printArray(int arr[], int size) {

cout << "Sorted array: ";
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

int main() {

int arr[] = {64, 34, 25, 12, 22, 11, 90};

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

bubbleSort(arr, size);
printArray(arr, size);

return 0;
}
OUTPUT:
EXPERIMENT – 13
Aim : To implement Selection Sorting.

Code:
#include <iostream>
using namespace std;

void selec onSort(int arr[], int size) {

for (int i = 0; i < size - 1; i++) {

// Find the minimum element in unsorted part

int minIndex = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}

// Swap the found minimum element with the first element

if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}

void printArray(int arr[], int size) {

cout << "Sorted array: ";
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

int main() {

int arr[] = {29, 10, 14, 37, 13};

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

selec onSort(arr, size);

printArray(arr, size);

return 0;
}
OUTPUT:
EXPERIMENT – 14
Aim : To implement Insertion Sorting.

Code:
#include <iostream>
using namespace std;

void inser onSort(int arr[], int size) {

for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;

// Move elements of arr[0..i-1] that are greater than key

// to one posi on ahead of their current posi on
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}

arr[j + 1] = key;
}
}

void printArray(int arr[], int size) {

cout << "Sorted array: ";
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

int main() {
int arr[] = {12, 11, 13, 5, 6};
int size = sizeof(arr) / sizeof(arr[0]);

inser onSort(arr, size);

printArray(arr, size);

return 0;
}

OUTPUT:
EXPERIMENT – 15
Aim : To implement Merge Sorting.
Code:

#include <iostream>
using namespace std;

// Merge two subarrays of arr[]

void merge(int arr[], int le , int mid, int right) {
int n1 = mid - le + 1;
int n2 = right - mid;

// Create temp arrays

int L[n1], R[n2];

// Copy data to temp arrays

for (int i = 0; i < n1; i++)
L[i] = arr[le + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];

// Merge the temp arrays back into arr[]

int i = 0, j = 0, k = le ;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy remaining elements of L[]

while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy remaining elements of R[]

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

// Merge sort func on

void mergeSort(int arr[], int le , int right) {
if (le < right) {
int mid = le + (right - le ) / 2;

// Sort first and second halves

mergeSort(arr, le , mid);
mergeSort(arr, mid + 1, right);

// Merge the sorted halves

merge(arr, le , mid, right);
}
}

// Func on to print the array

void printArray(int arr[], int size) {
cout << "Sorted array: ";
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

int main() {

int arr[] = {38, 27, 43, 3, 9, 82, 10};

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

mergeSort(arr, 0, size - 1);

printArray(arr, size);

return 0;
}

OUTPUT:
EXPERIMENT – 16
Aim : To implement Heap Sorting.
Code:
#include <iostream>
using namespace std;
void heapify(int arr[], int size, int i) {
int largest = i;
int le = 2 * i + 1;
int right = 2 * i + 2;

// If le child is larger than root

if (le < size && arr[le ] > arr[largest])
largest = le ;
// If right child is larger than largest so far
if (right < size && arr[right] > arr[largest])
largest = right;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, size, largest);
}
}
void heapSort(int arr[], int size) {
)
for (int i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);

// One by one extract an element from heap

for (int i = size - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
}
// Func on to print the array
void printArray(int arr[], int size) {
cout << "Sorted array: ";
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()

int arr[] = {12, 11, 13, 5, 6, 7};

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

heapSort(arr, size);
printArray(arr, size);
return 0;
}

OUTPUT:
EXPERIMENT – 17
Aim : To implement Matrix Multiplication by Strassen’s algorithm.

Code:
#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<int>> Matrix;

// Func on to add two matrices

Matrix add(Matrix A, Matrix B) {
int n = A.size();
Matrix result(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
result[i][j] = A[i][j] + B[i][j];
return result;
}

// Func on to subtract two matrices

Matrix subtract(Matrix A, Matrix B) {
int n = A.size();
Matrix result(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
result[i][j] = A[i][j] - B[i][j];
return result;
}

// Strassen's Matrix Mul plica on

Matrix strassen(Matrix A, Matrix B) {
int n = A.size();

if (n == 1) {
return {{A[0][0] * B[0][0]}};
}

int newSize = n / 2;
Matrix A11(newSize, vector<int>(newSize));
Matrix A12(newSize, vector<int>(newSize));
Matrix A21(newSize, vector<int>(newSize));
Matrix A22(newSize, vector<int>(newSize));

Matrix B11(newSize, vector<int>(newSize));

Matrix B12(newSize, vector<int>(newSize));
Matrix B21(newSize, vector<int>(newSize));
Matrix B22(newSize, vector<int>(newSize));

// Dividing matrices into 4 sub-matrices:

for (int i = 0; i < newSize; i++)
for (int j = 0; j < newSize; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + newSize];
A21[i][j] = A[i + newSize][j];
A22[i][j] = A[i + newSize][j + newSize];

B11[i][j] = B[i][j];
B12[i][j] = B[i][j + newSize];
B21[i][j] = B[i + newSize][j];
B22[i][j] = B[i + newSize][j + newSize];
}
// 7 recursive mul plica ons
Matrix M1 = strassen(add(A11, A22), add(B11, B22));
Matrix M2 = strassen(add(A21, A22), B11);
Matrix M3 = strassen(A11, subtract(B12, B22));
Matrix M4 = strassen(A22, subtract(B21, B11));
Matrix M5 = strassen(add(A11, A12), B22);
Matrix M6 = strassen(subtract(A21, A11), add(B11, B12));
Matrix M7 = strassen(subtract(A12, A22), add(B21, B22));

// Calcula ng the result submatrices

Matrix C11 = add(subtract(add(M1, M4), M5), M7);
Matrix C12 = add(M3, M5);
Matrix C21 = add(M2, M4);
Matrix C22 = add(subtract(add(M1, M3), M2), M6);

// Combining the 4 submatrices into one

Matrix C(n, vector<int>(n));
for (int i = 0; i < newSize; i++)
for (int j = 0; j < newSize; j++) {
C[i][j] = C11[i][j];
C[i][j + newSize] = C12[i][j];
C[i + newSize][j] = C21[i][j];
C[i + newSize][j + newSize] = C22[i][j];
}

return C;
}

// Func on to display matrix

void printMatrix(Matrix &matrix) {
for (auto &row : matrix) {
for (int val : row)
cout << val << " ";
cout << endl;
}
}

// Main Func on
int main() {
int n;
cout << "Enter size of matrices (power of 2): ";
cin >> n;

Matrix A(n, vector<int>(n));

Matrix B(n, vector<int>(n));

cout << "Enter elements of matrix A:\n";

for (auto &row : A)
for (int &x : row)
cin >> x;

cout << "Enter elements of matrix B:\n";

for (auto &row : B)
for (int &x : row)
cin >> x;

Matrix C = strassen(A, B);

cout << "Resultant Matrix C (A x B):\n";

printMatrix(C);

return 0;
}
OUTPUT:
EXPERIMENT – 18
Aim : Find Minimum Spanning Tree using Kruskal’s Algorithm.

Code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structure to represent an edge
struct Edge {
int u, v, weight;

bool operator<(const Edge& other) const {

return weight < other.weight;
}
};

// Disjoint Set Union (Union-Find)

class DSU {
vector<int> parent, rank;
public:
DSU(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; ++i)
parent[i] = i;
}

int find(int x) {
if (x != parent[x])
parent[x] = find(parent[x]); // Path compression
return parent[x];
}

bool unite(int x, int y) {

int xr = find(x);
int yr = find(y);
if (xr == yr) return false;

if (rank[xr] < rank[yr])

parent[xr] = yr;
else if (rank[xr] > rank[yr])
parent[yr] = xr;
else {
parent[yr] = xr;
rank[xr]++;
}
return true;
}
};

// Kruskal's Algorithm
int kruskalMST(int V, vector<Edge>& edges, vector<Edge>& mst) {
sort(edges.begin(), edges.end());

DSU dsu(V);
int mstWeight = 0;

for (auto& edge : edges) {

if (dsu.unite(edge.u, edge.v)) {
mst.push_back(edge);
mstWeight += edge.weight;
}
}
return mstWeight;
}

int main() {
cout << "Enter number of ver ces and edges: ";
int V, E;
cin >> V >> E;

vector<Edge> edges(E);
cout << "Enter edges in the format: u v weight\n";
for (int i = 0; i < E; ++i) {
cin >> edges[i].u >> edges[i].v >> edges[i].weight;
}

vector<Edge> mst;
int totalWeight = kruskalMST(V, edges, mst);

cout << "Minimum Spanning Tree edges:\n";

for (auto& edge : mst) {
cout << edge.u << " - " << edge.v << " : " << edge.weight << "\n";
}
cout << "Total weight of MST: " << totalWeight << endl;

return 0;
}
OUTPUT: