1

EXPERIMENT : 1 (a)
AIM : WAP to implement Merge Sort using array as a data structure & analyze its time and space
complexity .
 Compiler Requirement : Dev C++
 Algorithm :
In the following algorithm, arr is the given array, beg is the starting element, and end is the
last element of the array.
 MERGE_SORT(arr, beg, end)
 if beg < end
 set mid = (beg + end)/2
 MERGE_SORT(arr, beg, mid)
 MERGE_SORT(arr, mid + 1, end)
 MERGE (arr, beg, mid, end)
 end of if
 END MERGE_SORT

CODE :

#include <bits/stdc++.h>
using namespace std;

void merge(vector<int> &arr, int low, int mid, int high) {

vector<int> temp; // temporary array
int left = low; // starting index of left half of arr
int right = mid + 1; // starting index of right half of arr

//storing elements in the temporary array in a sorted manner//

while (left <= mid && right <= high) {
if (arr[left] <= arr[right]) {
temp.push_back(arr[left]);
left++;
}
else {
temp.push_back(arr[right]);
 2

right++;
}
}

// if elements on the left half are still left //

while (left <= mid) {
temp.push_back(arr[left]);
left++;
}

// if elements on the right half are still left //

while (right <= high) {
temp.push_back(arr[right]);
right++;
}
// transfering all elements from temporary to arr //
for (int i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
}
void mergeSort(vector<int> &arr, int low, int high) {
if (low >= high) return;
int mid = (low + high) / 2 ;
mergeSort(arr, low, mid); // left half
mergeSort(arr, mid + 1, high); // right half
merge(arr, low, mid, high); // merging sorted halves
}
int main() {
vector<int> arr = {25 , 11 , 4 , 73 , 95 , 48 , 20} ;
int n = 7;
 3

cout << "\t\tBefore Sorting Array: \n" << endl<<"\t";

for (int i = 0; i < n; i++) {
cout << arr[i] << " " ;
}
cout <<"\n"<<endl<<"--------------------------------\n\n";
mergeSort(arr, 0, n - 1);
cout << "\t\tAfter Sorting Array: \n" << endl<<"\t";
for (int i = 0; i < n; i++) {
cout << arr[i] << " " ;
}
cout <<endl;
return 0 ;
}

OUTPUT :

Complexity :
 Time Complexity : O(NlogN)

 Space Complexity : O(N)

 4

EXPERIMENT : 1 (b)
AIM : WAP to implement Quick Sort using array as a data structure and analyze its time and space
complexity.
 Compiler Requirement : Dev C++
 Algorithm :
In the following algorithm, A is the given array :-
qs (array A, start, end) {
if (start < end) {
p = partition(A, start, end)
qs (A, start, p - 1)
qs (A, p + 1, end)
}
}

CODE :

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int> &arr, int low, int high) {

int pivot = arr[low];
int i = low;
int j = high;

while (i < j) {
while (arr[i] <= pivot && i <= high - 1) {
i++;
}
while (arr[j] > pivot && j >= low + 1) {
j--;
}
if (i < j) swap(arr[i], arr[j]);
 5

}
swap(arr[low], arr[j]);
return j;
}
void qs(vector<int> &arr, int low, int high) {
if (low < high) {
int pIndex = partition(arr, low, high);
qs(arr, low, pIndex - 1);
qs(arr, pIndex + 1, high);
}
}
vector<int> quickSort(vector<int> arr) {
qs(arr, 0, arr.size() - 1);
return arr;
}
int main()
{
vector<int> arr = {4, 6, 2, 5, 7, 9, 1, 3};
int n = arr.size();
cout << "\n\t\tBefore Using quick Sort: \n" << endl<<"\t";
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl<<"----------------------------------\n";
arr = quickSort(arr);
cout << "\n\t\tAfter Using quick sort: \n\n"<<"\t";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
 6

cout << "\n";

return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(N*logN) , where N = size of the array

 Space Complexity : O(1) + O(N) auxiliary stack space

.
 7

EXPERIMENT : 1 (c)
AIM : WAP to implement Bubble Sort using array as a data structure and analyze its time and space
complexity .
 Compiler Requirement : Dev C++
 Algorithm :
In the following algorithm, A is the given array :-
Declare variables as i , j , temp;
for(i=0 -> i< n){
for(j = i+1 -> j < n) {
if(a[j] < a[i]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

CODE :

#include <bits/stdc++.h>
using namespace std;
void print(int a[], int n) {
int i;
for(i = 0; i < n; i++) {
cout << a[i] << " "; }
}
void bubble(int a[], int n) {
int i, j, temp;
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(a[j] < a[i]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
 8

}
}
}
int main () {
int i, j,temp;
int a[5] = { 10, 35, 32, 13, 26};
int n = sizeof(a)/sizeof(a[0]);
cout<<"\n\t\tBefore sorting array elements are - \n\n\t";
print(a, n);
cout<<"\n--------------------------------------------";
bubble(a, n);
cout<<"\n\t\tAfter sorting array elements are - \n\n\t";
print(a, n);
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(N2) , where N = size of the array

 Space Complexity : O(1)

 9

EXPERIMENT : 1 (d)
AIM : WAP to implement Selection Sort using array as a data structure and analyze its time and space
complexity .
 Compiler Requirement : Dev C++
 Algorithm :
In the following algorithm, A is the given array :-
Declaring a function to perform selection sort..
for(i=0 -> i<n){
mini = i
for(j=i+1 -> j<n){
if(arr[j] < arr[mini])
mini = j;
}
swap( arr[i] , arr[mini])
}

CODE :

#include<bits/stdc++.h>
using namespace std;
void selection_sort(int arr[], int n) {
for(int i=0 ;i<n-1 ;i++){
int mini = i;
for(int j=i+1 ; j<n ;j++){
if(arr[j] < arr[mini]){
mini = j;
}
}
int temp = arr[mini];
arr[mini] = arr[i];
arr[i] = temp;
}
cout<<"\n----------------------------------\n";
cout << "\t\tAfter Selection Sort" << endl<<"\t";
 10

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

cout << arr[i] << " ";
}
}
int main(){
int arr[] = {13,46,24,52,20,9};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "\t\tBefore selection sort: " << "\n\t";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
selection_sort(arr, n);
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(N2) , where N = size of the array

 Space Complexity : O(1)

 11

EXPERIMENT : 1 (e)
AIM : WAP to implement Heap Sort using array as a data structure and analyze its time and space
complexity .
 Compiler Requirement : Dev C++
 Algorithm :

HeapSort(arr)
BuildMaxHeap(arr)
i = length(arr) to 2
swap arr[1] with arr[i]
heap_size[arr] = heap_size[arr] ? 1
MaxHeapify(arr,1)
End

BuildMaxHeap(arr)
heap_size(arr) = length(arr)
for i = length(arr)/2 to 1
MaxHeapify(arr,i)
End

MaxHeapify(arr,i)
L = left(i) R = right(i)
if L ? heap_size[arr] and arr[L] > arr[i]
largest = L
else largest = i
if R ? heap_size[arr] and arr[R] > arr[largest]
largest = R
if largest != i
swap arr[i] with arr[largest]
MaxHeapify(arr,largest)
End

CODE :

#include <iostream>
using namespace std;
void heapify(int a[], int n, int i){
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
 12

if (left < n && a[left] > a[largest])

largest = left;

if (right < n && a[right] > a[largest])

largest = right;
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, n, largest);
}
}
void heapSort(int a[], int n){
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
for (int i = n - 1; i >= 0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, i, 0);
}
}
void printArr(int a[], int n) {
for (int i = 0; i < n; ++i) {
cout<<a[i]<<" ";
}
}
int main() {
int a[] = {47, 9, 22, 42, 27, 25, 0};
int n = sizeof(a) / sizeof(a[0]);
 13

cout<<"\t\tBefore sorting array elements are - \n\t";

printArr(a, n);
cout<<"\n--------------------------------------";
heapSort(a, n);
cout<<"\n\t\tAfter sorting array elements are - \n\t";
printArr(a, n);
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(NlogN) , where N = size of the array

 Space Complexity : O(1)

.
 14

EXPERIMENT : 2 (a)
AIM : WAP to implement Linear Search and analyze its time complexity .
 Compiler Requirement : Dev C++
 Theory :
Linear Search (also known as Sequential Search) is a straightforward algorithm used to find a specific
value within a list or array. The algorithm working is as follows :--

 Starting Point: Begin at the first element of the list or array.

 Comparison: Compare the current element with the target value.
 Traversal: Move sequentially to the next element in the list or array.
 Match Found: If the current element matches the target value, the search is successful, and the
index of the target is returned.
 End of List: If the end of the list or array is reached without finding the target value, the search
concludes that the target is not present in the list.

Linear search is typically used when dealing with unsorted or small lists, where sorting the list would be
inefficient compared to a simple search.
 Algorithm :

 Start: Initialize the index i to 0.

 Check Current Element : --
Compare the current element arr[i] with the target value.
If arr[i] == target, go to step 5 (Target found).
 Move to Next Element : --
Increment the index i by 1.
If i < n, go back to step 2 (Check the next element).
 End of List : --
If i >= n, the end of the list is reached without finding the target.
Proceed to step 6 (Target not found).
 Target Found : --
Return the index i where the target value is found.
 Target Not Found : --
Return -1, indicating that the target value is not present in the array

CODE :

#include <iostream>
using namespace std;
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; ++i) {
if (arr[i] == target) {
 15

return i;
}
}
return -1;
}
int main() {
int n, target;
cout << "Enter the number of elements: ";
cin >> n;
int *arr = new int[n];
cout << "Enter the elements:\n";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cout << "Enter the target element to search for: ";
cin >> target;
int result = linearSearch(arr, n, target);
if (result != -1) {
cout << "\n-----------------------------------\n";
cout << "Element found at index " << result << endl;
} else {
cout << "\n-----------------------------------\n";
cout << "Element not found\n";
}
delete[] arr;
return 0;
}

OUTPUT :
 16

Complexity :
 Time Complexity :

 Best Case: O(1) , The best-case scenario occurs when the target value is found at the very first
position of the list or array. Here, the algorithm only needs one comparison.

 Average Case: O(n) , On average, if the target value is located somewhere in the middle of the list,
the algorithm will need to traverse approximately half of the elements.

 Worst Case: O(n) , The worst-case scenario occurs when the target value is either not present in
the list or is found at the very last position. In this case, the algorithm needs to check every single
element in the list.

 Space Complexity : O(1) .

 17

EXPERIMENT : 2 (b)
AIM : WAP to implement Binary Search and analyze its time complexity.
 Compiler Requirement : Dev C++
 Theory :

Binary Search is a highly efficient algorithm used to find a specific value within a sorted array or list. The
key idea behind binary search is to repeatedly divide the search interval in half, thereby reducing the
problem size exponentially with each step. This method leverages the sorted nature of the array to
quickly zero in on the target value.

 Algorithm :

 Initialization:
o Set two pointers: left to the index of the first element (0) and right to the
index of the last element (n - 1 where n is the number of elements in the
array).
 Calculate the Middle:
o Compute the middle index of the current interval using :-
Mid = left + ( right – left ) / 2
 Comparison:
o Compare the target value with the element at the middle index :-
 If the target is equal to the middle element: The target is found.
Return the middle index.
 If the target is less than the middle element: Adjust the right
pointer to mid - 1 (narrow the search to the left half).
 If the target is greater than the middle element: Adjust the left
pointer to mid + 1 (narrow the search to the right half).
 Repeat:
o Repeat steps 2 and 3 until the left pointer exceeds the right pointer. If
the target value is not found after the pointers cross, return -1 or another
indication that the value is not present in the array.

CODE :

#include <algorithm>
#include <iostream>
using namespace std;
int binarySearch(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
 18

while (left <= right) {

int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int n, target;
cout << "Enter the number of elements: ";
cin >> n;
int *arr = new int[n];
cout << "Enter the elements:\n";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cout << "Enter the target element to search for: ";
cin >> target;
sort(arr, arr + n);
cout << "\n\tArray sorted for Binary Search:\n";
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << "\t\n";
 19

int result = binarySearch(arr, n, target);

if (result != -1) {
cout << "--------------------------------\n\t";
cout << "Element found at index " << result << endl;
} else {
cout << "\n--------------------------------\n\t";
cout << "Element not found !\n";
}
delete[] arr;
return 0;
}

OUTPUT :

.
 20

Complexity :
 Time Complexity :

 Best Case: O(1) , The best case occurs when the target value is located at the middle index
of the array on the first comparison.

 Average Case: O(log n) , On average, binary search will require log₂(n) comparisons, where
n is the number of elements in the array, because the search space is halved with each
step.

 Worst Case: O(log n) , In the worst case, binary search requires log₂(n) comparisons when
the target is located at the far end of the search space or not present in the array

 Space Complexity :

 Iterative Version: O(1) , When implemented iteratively, binary search requires a constant
amount of extra space, as it only uses a few additional variables for pointers and indices.

 Recursive Version: O(log n) , When implemented recursively, the space complexity is O(log n)
due to the function call stack. Each recursive call adds a new frame to the call stack, and the
maximum depth of recursion is proportional to the logarithm of the number of elements
 21

EXPERIMENT : 3
AIM : WAP to implement Matrix multiplication & analyze its time complexity.
 Compiler Requirement : Dev C++
 Theory :
Strassen's Matrix Multiplication is the divide and conquer approach to solve the matrix multiplication
problems. The usual matrix multiplication method multiplies each row with each column to achieve the
product matrix. The time complexity taken by this approach is O(n3), since it takes two loops to multiply.
Strassen’s method was introduced to reduce the time complexity from O(n3) to O(nlog 7).
 Algorithm :
In this context, using Strassen’s Matrix multiplication algorithm, the time consumption can be
improved a little bit.

Strassen’s Matrix multiplication can be performed only on square matrices where n is

a power of 2. Order of both of the matrices are n × n.
Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below –

Using Strassen’s Algorithm compute the following : −

M1:=(A+C)×(E+F)M1:=(A+C)×(E+F)
M2:=(B+D)×(G+H)M2:=(B+D)×(G+H)
M3:=(A−D)×(E+H)M3:=(A−D)×(E+H)
M4:=A×(F−H)M4:=A×(F−H)
M5:=(C+D)×(E)M5:=(C+D)×(E)
M6:=(A+B)×(H)M6:=(A+B)×(H)
M7:=D×(G−E)M7:=D×(G−E)
Then,
I:=M2+M3−M6−M7I:=M2+M3−M6−M7
J:=M4+M6J:=M4+M6
K:=M5+M7K:=M5+M7
L:=M1−M3−M4−M5
 Analysis

Using this recurrence relation, we get T(n)=O(nlog7)

Hence, the complexity of Strassen’s matrix multiplication algorithm is O(nlog7).

 22

CODE :

#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<int>> Matrix;
Matrix add(const Matrix &A, const Matrix &B) {
int n = A.size();
Matrix C(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
C[i][j] = A[i][j] + B[i][j];
}
}
return C;
}
Matrix subtract(const Matrix &A, const Matrix &B) {
int n = A.size();
Matrix C(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
C[i][j] = A[i][j] - B[i][j];
}
}
return C;
}
Matrix strassen(const Matrix &A, const Matrix &B) {
int n = A.size();
if (n == 1) {
Matrix C(1, vector<int>(1));
C[0][0] = A[0][0] * B[0][0];
 23

return C;
}
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));
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];
}
}
Matrix P1 = strassen(add(A11, A22), add(B11, B22));
Matrix P2 = strassen(add(A21, A22), B11);
Matrix P3 = strassen(A11, subtract(B12, B22));
Matrix P4 = strassen(A22, subtract(B21, B11));
Matrix P5 = strassen(add(A11, A12), B22);
Matrix P6 = strassen(subtract(A21, A11), add(B11, B12));
Matrix P7 = strassen(subtract(A12, A22), add(B21, B22));
 24

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

Matrix C11 = add(subtract(add(P1, P4), P5), P7);
Matrix C12 = add(P3, P5);
Matrix C21 = add(P2, P4);
Matrix C22 = add(subtract(add(P1, P3), P2), P6);
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;
}
void printMatrix(const Matrix &M) {
int n = M.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << M[i][j] << " ";
}
cout << endl;
}
}
int main() {
Matrix A = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
 25

};
Matrix B = {
{16, 15, 14, 13},
{12, 11, 10, 9},
{8, 7, 6, 5},
{4, 3, 2, 1}
};
cout << "Matrix A:" << endl;
printMatrix(A);
cout << "Matrix B:" << endl;
printMatrix(B);
Matrix C = strassen(A, B);
cout << "Matrix C (A * B):" << endl;
printMatrix(C);
return 0;
}

OUTPUT :
 26

Complexity :

 Time Complexity :

 Best Case Time Complexity : O(n2.81)

 Average Case Time Complexity : O(n2.81)

 Worst Case Time Complexity : O(n2.81)

 Space Complexity : O(N2)

.
 27

EXPERIMENT : 4
AIM : WAP to implement solution for knapsack problem using greedy method.
 Compiler Requirement : Dev C++
 Algorithm :
In this , A set of n items, where each item i has a value v[i] and a weight w[i] id taken as input
.The maximum capacity of the knapsack is W. The maximum value that can be
accommodated in the knapsack, possibly with fractional parts of items as the output .

 Calculate the value-to-weight ratio for each item:

ratio[i]=v[i] / w[i]
 Sort items by this ratio in descending order.
 Initialize total value as 0 and current weight as 0.
 Add items to the knapsack:
For each item in sorted order:
 If it fits, add it fully and update the total value.
 If not, add a fraction of it to fill the knapsack and break.

CODE :

#include <bits/stdc++.h>
using namespace std;

struct Item {
int value, weight;

Item(int value, int weight)

: value(value), weight(weight) { }
};

bool cmp(struct Item a, struct Item b) {

double r1 = (double)a.value / a.weight;
double r2 = (double)b.value / b.weight;
return r1 > r2;
}
 28

double fractionalKnapsack(struct Item arr[],int N, int size) {

sort(arr, arr + size, cmp);

int curWeight = 0;

double finalvalue = 0.0;

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

if (curWeight + arr[i].weight <= N) {
curWeight += arr[i].weight;
finalvalue += arr[i].value;
}
else {
int remain = N - curWeight;
finalvalue += arr[i].value * ((double)remain / arr[i].weight);
break;
}
}
return finalvalue;
}
int main() {
int N = 60;

Item arr[] = { { 100, 10 },

{ 280, 40 },
{ 120, 20 },
{ 120, 24 } };

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

 29

cout << "\n\tMaximum profit earned = "

<< fractionalKnapsack(arr, N, size);
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(N*LogN)

 Space Complexity : O(N)

.
 30

EXPERIMENT : 5
AIM : WAP to implement job sequencing with deadlines .
 Compiler Requirement : Dev C++
 Algorithm :
Input is n jobs, each with a profit p[i] and a deadline d[i] .

 Sort jobs in decreasing order of profit. This ensures that more profitable jobs are
considered first.
 Initialize a schedule with max_deadline slots (equal to the maximum deadline
among the jobs), initially all set to empty.
 Iterate over each job:
o For each job i, find the latest available time slot before its deadline (d[i]).
o If a slot is found, assign the job to that slot and add its profit to the total.
 Stop once all jobs have been considered or all slots are filled.

CODE :

#include <algorithm>
#include <iostream>
using namespace std;

struct Job {
char id;
int dead;
int profit;
};

bool comparison(Job a, Job b){

return (a.profit > b.profit);
}
void printJobScheduling(Job arr[], int n){
sort(arr, arr + n, comparison);

int result[n];
 31

bool slot[n];

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

slot[i] = false;

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

for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {
if (slot[j] == false) {
result[j] = i;
slot[j] = true;
break;
}
}
}
for (int i = 0; i < n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}

int main(){
Job arr[] = { { 'a', 2, 100 },
{ 'b', 1, 19 },
{ 'c', 2, 27 },
{ 'd', 1, 25 },
{ 'e', 3, 15 } };

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

cout << "Following is maximum profit sequence of jobs :--\n\n";
printJobScheduling(arr, n);
return 0;
 32

OUTPUT :

Complexity :
 Time Complexity : O(n²)

 Space Complexity : O(n)

.
 33

EXPERIMENT : 6
AIM : WAP to implement Huffman coding and analyze its time complexity .
 Compiler Requirement : Dev C++
 Algorithm :
Input A set of n characters, each with a frequency f[i] representing how often they occur
and in output , the Huffman codes for each character and the binary encoded data.

 Build a priority queue (min-heap) where each element is a node containing a

character and its frequency. The node with the lowest frequency has the highest
priority.
 Construct the Huffman tree:

 While there is more than one node in the queue:

o Extract the two nodes with the smallest frequencies.

o Create a new internal node with these two nodes as children. The
frequency of this new node is the sum of the two extracted nodes.
o Insert this new node back into the priority queue.

 Repeat until there is only one node left, which will be the root of the Huffman
tree.

 Generate Huffman Codes:

Traverse the Huffman tree from the root to each leaf node (character). Assign a
binary code to each character: append a 0 for left traversal and a 1 for right traversal.

CODE :

#include <bits/stdc++.h>
using namespace std;
struct MinHeapNode {
char data;
unsigned freq;
MinHeapNode *left, *right;
MinHeapNode(char data, unsigned freq){
left = right = NULL;
this->data = data;
 34

this->freq = freq;
}
};
struct compare {
bool operator()(MinHeapNode* l, MinHeapNode* r) {
return (l->freq > r->freq);
}
};
void printCodes(struct MinHeapNode* root, string str) {
if (!root)
return;
if (root->data != '$')
cout << root->data << ": " << str << "\n";
printCodes(root->left, str + "0");
printCodes(root->right, str + "1");
}
void HuffmanCodes(char data[], int freq[], int size) {
struct MinHeapNode *left, *right, *top;
priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare>
minHeap;
for (int i = 0; i < size; ++i)
minHeap.push(new MinHeapNode(data[i], freq[i]));
while (minHeap.size() != 1) {
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
top = new MinHeapNode('$',
left->freq + right->freq);
top->left = left;
 35

top->right = right;
minHeap.push(top);
}
printCodes(minHeap.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 :

Complexity :
 Time Complexity : O(n log n)

 Space Complexity : O(n)

.
 36

EXPERIMENT : 7 (a)
AIM : WAP to implement minimum spanning tree using Prim’s Algorithm and analyze its time & space
complexity.
 Compiler Requirement : Dev C++
 Algorithm :
Follow the given steps to utilize the Prim’s Algorithm mentioned above for finding MST of a
graph:
 Create a set mstSet that keeps track of vertices already included in MST.
 Assign a key value to all vertices in the input graph. Initialize all key values as
INFINITE. Assign the key value as 0 for the first vertex so that it is picked first.
 While mstSet doesn’t include all vertices
o Pick a vertex u that is not there in mstSet and has a minimum key value.
o Include u in the mstSet.
o Update the key value of all adjacent vertices of u. To update the key values,
iterate through all adjacent vertices.
o For every adjacent vertex v, if the weight of edge u-v is less than the previous
key value of v, update the key value as the weight of u-v.

CODE :

#include <bits/stdc++.h>
using namespace std;
#define V 5

int minKey(int key[], bool mstSet[]){

int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
 37

void printMST(int parent[], int graph[V][V]){

cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t"
<< graph[i][parent[i]] << " \n";
}

void primMST(int graph[V][V]){

int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false
&& graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}

int main(){
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
 38

{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
primMST(graph);
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(V2) using an adjacency matrix and O((V +E) log V) using an adjacency list, where
V is the number of vertices and E is the number of edges in the graph

 Space Complexity : O(V+E) for the priority queue and O(V2) for the adjacency matrix representation

.
 39

EXPERIMENT : 7 (b)
AIM : WAP to implement minimum spanning tree using Kruskal’s Algorithm and analyze its time & space
complexity.
 Compiler Requirement : Dev C++
 Algorithm :
The inputs taken by the kruskal’s algorithm are the graph G {V, E}, where V is the
set of vertices and E is the set of edges, and the source vertex S and the minimum
spanning tree of graph G is obtained as an output.

 Sort all the edges in the graph in an ascending order and store it in
an array edge[].
 Construct the forest of the graph on a plane with all the vertices in
it.
 Select the least cost edge from the edge[] array and add it into the
forest of the graph. Mark the vertices visited by adding them into
the visited[] array.
 Repeat the steps 2 and 3 until all the vertices are visited without
having any cycles forming in the graph
 When all the vertices are visited, the minimum spanning tree is
formed.
 Calculate the minimum cost of the output spanning tree formed.

CODE :

#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;
 40

}
}
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;
}
else if (rank[s1] > rank[s2]) {
parent[s2] = s1;
}
else {
parent[s2] = s1;
rank[s1] += 1;
}
}
}
};

class Graph {
vector<vector<int> > edgelist;
int V;
public:
Graph(int V) { this->V = V; }
 41

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

g.addEdge(0, 3, 5);
g.kruskals_mst();
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(E logV), here E is number of Edges and V is number of vertices in graph

 Space Complexity : O(V + E), here V is the number of vertices and E is the number of edges in the
graph.

.
 43

EXPERIMENT : 8
AIM : WAP to implement Dijkstra’s Algorithm and analyze its complexity.
 Compiler Requirement : Dev C++
 Algorithm :
Create a set sptSet (shortest path tree set) that keeps track of vertices included in the
shortest path tree, i.e., whose minimum distance from the source is calculated and finalized.
Initially, this set is empty.
 Assign a distance value to all vertices in the input graph. Initialize all distance values
as INFINITE. Assign the distance value as 0 for the source vertex so that it is picked
first.
 While sptSet doesn’t include all vertices
o Pick a vertex u which is not there in sptSet and has minimum distance
value.
o Include u to sptSet.
o Update the distance value of all adjacent vertices of u. To update the
distance values, iterate through all adjacent vertices. For every adjacent
vertex v, if the sum of the 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.

CODE :

#include <limits.h>
#include <stdio.h>
#define V 9
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;
}

void printSolution(int dist[], int n){

printf("Vertex Distance from Source\n");
 44

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

printf("\t%d \t\t\t\t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src){

int dist[V];
bool sptSet[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 },
 45

{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(V2)

 Space Complexity : O(V)

.
 46

EXPERIMENT : 9
AIM : WAP to implement Bellman Ford algorithm and analyze its time & space complexities .
 Compiler Requirement : Dev C++
 Algorithm :
Shortest distance to all vertices from src (source vertex). If there is a negative weight cycle,
then shortest distances are not calculated, negative weight cycle is reported.
 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.
 This step calculates shortest distances. Do following |V|-1 times where |V| is the
number of vertices in given graph. 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
 This step reports if there is a negative weight cycle in graph. Do following for each
edge u-v :--
 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

CODE :

#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];
 47

}
}
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;
int E = 8;
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;
}
 48

OUTPUT :

Complexity :
 Time Complexity : O(VE) , where V is no. of vertices & E is no. of edges

 Space Complexity : O(V)

 49

EXPERIMENT : 10
AIM : WAP to implement N – Queen’s Problem using backtracking .
 Compiler Requirement : Dev C++
 Algorithm :
 Start in the leftmost column
 If all queens are placed return true
 Try all rows in the current column. Do the following for every row.
o If the queen can be placed safely in this row
 Then mark this [row, column] as part of the solution and recursively
check if placing queen here leads to a solution.
 If placing the queen in [row, column] leads to a solution then
return true.
 If placing queen doesn’t lead to a solution then unmark this [row,
column] then backtrack and try other rows.
o If all rows have been tried and valid solution is not found return false to
trigger backtracking.

CODE :

#include <bits/stdc++.h>
using namespace std;

void printSolution(vector<vector<int>>& board) {

int n = board.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
if(board[i][j])
cout << "Q ";
else
cout << ". ";
cout << "\n";
}
}
 50

bool isSafe(vector<vector<int>>& board,int row, int col) {

int n = board.size();
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 &&
j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 &&
i < n; i++, j--)
if (board[i][j])
return false;
return true;
}

bool solveNQUtil(vector<vector<int>>& board, int col) {

int n = board.size();
if (col >= n)
return true;
for (int i = 0; i < n; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
board[i][col] = 0;
}
}
return false;
 51

bool solveNQ(int n) {
vector<vector<int>> board(n, vector<int>(n, 0));
if (solveNQUtil(board, 0) == false) {
cout << "Solution does not exist";
return false;
}
printSolution(board);
return true;
}

int main() {
int n = 4;
solveNQ(n);
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(N!)

 Space Complexity : O(N2)

 52

EXPERIMENT : 11
AIM : WAP to implement Matrix Chain Multiplication via dynamic programming and analyze its
complexity .
 Compiler Requirement : Dev C++
 Algorithm :

 Define a DP Table m[][]m[][]m[][]:

 Let m[i][j]m[i][j]m[i][j] represent the minimum number of scalar multiplications

required to compute the product of matrices AiA_iAi through AjA_jAj.

 Base Case Initialization:

 Set m[i][i]=0m[i][i] = 0m[i][i]=0 for all iii, as multiplying a single matrix incurs no
multiplication cost.

 Recurrence Relation:

 For each possible chain length L=2L = 2L=2 to nnn:

o For each possible starting index i=1i = 1i=1 to n−L+1n - L + 1n−L+1:

 Compute the ending index j=i+L−1j = i + L - 1j=i+L−1.
 Initialize m[i][j]m[i][j]m[i][j] to infinity.
 For each possible split point k=ik = ik=i to j−1j-1j−1:
 Compute cost q=m[i][k]+m[k+1][j]+p[i−1]×p[k]×p[j]q = m[i][k] + m[k+1][j]
+ p[i-1] \times p[k] \times
 p[j]q=m[i][k]+m[k+1][j]+p[i−1]×p[k]×p[j].
 Update m[i][j]=min⁡(m[i][j],q)m[i][j] = \min(m[i][j],
q)m[i][j]=min(m[i][j],q).

 Return the Result:

 The minimum cost of multiplying all matrices from A1A_1A1 to AnA_nAn is stored in
m[1][n]m[1][n]m[1][n].

CODE :

#include <iostream>
#include <limits.h>
using namespace std;
 53

int matrixChainOrder(int p[], int n) {

int m[n][n];
int s[n][n];
for (int i = 1; i < n; i++)
m[i][i] = 0;

for (int L = 2; L <= n; L++) {

for (int i = 1; i <= n - L + 1; i++) {
int j = i + L - 1;
m[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j]) {
m[i][j] = q;
s[i][j] = k;
}
}
}
}
cout << "Cost of multiplying specific pairs:\n";
for (int i = 1; i < n; i++) {
for (int j = i; j < n; j++) {
cout << "Cost of multiplying A" << i << " to A" << j << ": " << m[i][j]<<
endl;
}
}
return m[1][n - 1];
}
int main() {
// Dimensions of matrices A1(5x4), A2(4x6), A3(6x2), A4(2x7)
int arr[] = {5, 4, 6, 2, 7};
 54

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

int totalCost = matrixChainOrder(arr, n);
cout << "Total minimum cost of multiplying all matrices: " << totalCost<< endl;
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(n3) .

 Space Complexity : O(n2) .

 55

EXPERIMENT : 12
AIM : WAP to implement Longest Common Sub – Sequence and analyze its complexity .
 Compiler Requirement : Dev C++
 Algorithm :
 Define a DP Table dp[][]dp[][]dp[][]:

 Let dp[i][j]dp[i][j]dp[i][j] represent the length of the LCS of the substrings

X[0…i−1]X[0 \dots i-1]X[0…i−1] and Y[0…j−1]Y[0 \dots j-1]Y[0…j−1].

 Base Case Initialization:

 If either string is empty, then dp[i][0]=0dp[i][0] = 0dp[i][0]=0 and dp[0][j]=0dp[0][j]

= 0dp[0][j]=0 for all iii and jjj, as the LCS with an empty string is 0.

 Recurrence Relation:

 For i=1i = 1i=1 to mmm and j=1j = 1j=1 to nnn:

o If X[i−1]==Y[j−1]X[i-1] == Y[j-1]X[i−1]==Y[j−1], then dp[i][j]=dp[i−1][j−1]+1dp[i][j]
= dp[i-1][j-1] + 1dp[i][j]=dp[i−1][j−1]+1 (extend the LCS by one character).
o Otherwise, dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])dp[i][j] = \max(dp[i-1][j], dp[i][j-
1])dp[i][j]=max(dp[i−1][j],dp[i][j−1]) (exclude the character from either XXX or
YYY to maximize the LCS).

 Return the Result:

 The length of the LCS of XXX and YYY is stored in dp[m][n]dp[m][n]dp[m][n].

CODE :

#include <cstring>
#include <iostream>
using namespace std;

void lcsAlgo(char *S1, char *S2, int m, int n) {

int LCS_table[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
 56

LCS_table[i][j] = 0;
else if (S1[i - 1] == S2[j - 1])
LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1;
else
LCS_table[i][j] = max(LCS_table[i - 1][j], LCS_table[i][j - 1]);
}
}

int index = LCS_table[m][n];

char lcsAlgo[index + 1];
lcsAlgo[index] = '\0';

int i = m, j = n;
while (i > 0 && j > 0) {
if (S1[i - 1] == S2[j - 1]) {
lcsAlgo[index - 1] = S1[i - 1];
i--;
j--;
index--;
}
else if (LCS_table[i - 1][j] > LCS_table[i][j - 1])
i--;
else
j--;
}
cout << "S1 : " << S1 << "\nS2 : " << S2 << "\nLCS: " << lcsAlgo << "\n";
}

int lcs(char *S1, char *S2, int m, int n) {

int L[m + 1][n + 1];
 57

int i, j;
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (S1[i - 1] == S2[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
return L[m][n];
}

int main() {
char S1[] = "ACADB";
char S2[] = "CBDA";
int m = strlen(S1);
int n = strlen(S2);

lcsAlgo(S1, S2, m, n);

printf("Length of LCS is %d\n", lcs(S1, S2, m, n));

}
 58

OUTPUT :

Complexity :
 Time Complexity : O(m*n) , where m & n are the lengths of the two strings .

 Space Complexity : O(max(m,n)) , where m & n are the lengths of the two strings .
 59

EXPERIMENT : 13
AIM : WAP to implement all pairs shortest path problem using Floyd’s Warshell algorithm. Parallelize
this algo, implement it and determine the speed-up achieved .
 Compiler Requirement : Dev C++
 Algorithm :
 Initialize the solution matrix same as the input graph matrix as a first step.
 Then update the solution matrix by considering all vertices as an intermediate
vertex.
 The idea is to pick all vertices one by one and updates all shortest paths which include
the picked vertex as an intermediate vertex in the shortest path.
 When we pick vertex number k as an intermediate vertex, we already have
considered vertices {0, 1, 2, .. k-1} as intermediate vertices.
 For every pair (i, j) of the source and destination vertices respectively, there are two
possible cases.
 k is not an intermediate vertex in shortest path from i to j. We keep the value
of dist[i][j] as it is.
 k is an intermediate vertex in shortest path from i to j. We update the value
of dist[i][j] as dist[i][k] + dist[k][j], if dist[i][j] > dist[i][k] + dist[k][j]

CODE :

#include <bits/stdc++.h>
#include <omp.h> // Include OpenMP header for parallelization
using namespace std;
#define V 4
#define INF 99999
void printSolution(int dist[][V]);
void floydWarshall(int dist[][V]) {
int i, j, k;
for (k = 0; k < V; k++) {
#pragma omp parallel for private(i, j)
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][j] > (dist[i][k] + dist[k][j]) && (dist[k][j] != INF &&
dist[i][k] != INF))
 60

dist[i][j] = dist[i][k] + dist[k][j];

}
}
}
printSolution(dist);
}
void printSolution(int dist[][V]) {
cout << "The following matrix shows the shortest distances\nbetween every pair
of vertices & result \nafter parallelization :\n\n";
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
cout << "INF ";
else
cout << dist[i][j] << " ";
}
cout << endl;
}
}
int main() {
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int graph[V][V] = { { 0, 5, INF, 10 },
{ INF, 0, 3, INF },
 61

{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };

Cout<<”the input grapgh is :\n\n”<<graph[v][v]<<”\n”;

floydWarshall(graph);
return 0;
}

OUTPUT :

Complexity :
 Time Complexity : O(V3), where V is the number of vertices. This can be very slow for large graphs.

 Space Complexity : O(V2) is manageable for graphs with a relatively small number of vertices.
However, for very large graphs, such as those with thousands or millions of vertices, the space
requirement can become a constraint due to memory limitations.

..
 62

EXPERIMENT : 14 (a)
AIM : WAP to implement Naive String Matching algorithm and analyze its time and space complexity .
 Compiler Requirement : Dev C++
 Algorithm :

 Let n be the length of text and m be the length of pattern.

 Iterate through the text from index i = 0 to i = n - m (inclusive):

 For each i, do the following:

 Initialize j to 0.
 Compare text[i + j] with pattern[j] for each j from 0 to m - 1.
 If text[i + j] equals pattern[j] for all j, the pattern is found at index i.
 If a mismatch is found at any j, break out of the inner loop and move to the next i.
 If a complete match is found at index i, print i.
 If no match is found after checking all positions, output "Pattern not found".

CODE :

#include <iostream>

#include <string>

using namespace std;

void search(string& pat, string& txt) {

int M = pat.size();

int N = txt.size();

for (int i = 0; i <= N - M; i++) {

int j;

for (j = 0; j < M; j++) {

 63

if (txt[i + j] != pat[j]) {

break;
}
}
if (j == M) {

cout << "Pattern found at index " << i << endl;

}
}
}

int main() {
// Example 1

string txt1 = "AABAACAADAABAABA";

string pat1 = "AABA";
cout << "Example 1: \n\t\tAABAACAADAABAABA\n\t\tAABA\n" << endl;

search(pat1, txt1);

// Example 2

string txt2 = "agd";

string pat2 = "g";

cout<<"\n--------------------------------\n";
cout << "\nExample 2: \n\t\tagd\n\t\tg\n" << endl;

search(pat2, txt2);
 64

return 0;
}

OUTPUT :

Complexity :
 Time Complexity :
Worst-case: O((n−m+1)×m) – occurs when there are many repeated characters, causing maximum
checks at each step.
Best-case: O(n) – occurs when a match is found quickly or there are no matches.

 Space Complexity : O(1) – no additional data structures are used other than loop counters and a few
auxiliary variables.

..
 65

EXPERIMENT : 14 (b)
AIM : WAP to implement Rabin Karp algorithm and analyze its time and space complexity .
 Compiler Requirement : Dev C++
 Algorithm :
 Let n be the length of text and m be the length of pattern.
 Calculate the hash value of pattern (p) and the initial hash value of the first m
characters of text (t).
 Loop through text from i = 0 to n - m:
 If p == t, check each character of pattern with the corresponding substring in
text to confirm the match.
 If confirmed, print i as the index where the pattern is found.
 Calculate the hash value for the next window of text (t[i+1]) using the rolling hash
formula:
t[i+1] = (d * (t[i] - text[i] * h) + text[i + m]) % q
 Where d is the number of characters in the input alphabet.
 h is the value of d^(m-1) % q to shift the hash window.
 Repeat until the end of text.

CODE :

#include <bits/stdc++.h>
using namespace std;

//number of characters in the input alphabet

#define d 256

/* pat -> pattern

txt -> text
q -> A prime number
*/
void search(char pat[], char txt[], int q)
{
int M = strlen(pat);
int N = strlen(txt);
int i, j;
 66

int p = 0; // hash value for pattern

int t = 0; // hash value for txt
int h = 1;

for (i = 0; i < M - 1; i++)

h = (h * d) % q;

for (i = 0; i < M; i++) {

p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0; i <= N - M; i++) {
if (p == t) {
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j]) {
break;
}
}
if (j == M)
cout << "Pattern found at index " << i
<< endl;
}
if (i < N - M) {
t = (d * (t - txt[i] * h) + txt[i + M]) % q;
if (t < 0)
t = (t + q);
}
}
}
 67

int main(){
char txt[] = "Legends spoke of a fearsome pirate known for his quick wit and
unmatched sword skills.The old captain warned the crew of the dangers of pirate-
infested waters.In his journal, the explorer recounted tales of pirate attacks and lost
treasures.";
char pat[] = "pirate";
int q = INT_MAX;
search(pat, txt, q);
return 0;
}

OUTPUT :

Complexity :
 Time Complexity :

Best case time complexity: O(n + m)

Average case time complexity: O(n + m)
Worst case time complexity: O(nm)
where n is the length of the text being searched and m is the length of the pattern
being searched for.

 Space Complexity : O(m)

..
 68

EXPERIMENT : 14 (c)
AIM : WAP to implement Knuth Morris Pratt algorithm and analyze its time and space complexity .
 Compiler Requirement : Dev C++
 Algorithm :
 Preprocess the Pattern:
Create the LPS (Longest Prefix Suffix) array, which stores the lengths of the
longest proper prefixes of the pattern that are also suffixes for each position in
the pattern.
 Initialize Indices:
Set two pointers: i for the text (initially 0) and j for the pattern (initially 0).
 Search for the Pattern:
o Compare characters of the pattern and text using the indices:
 If pattern[j] == text[i], increment both i and j.
 If j equals the length of the pattern, a match is found at index i - j. Update
j using the LPS array.
 Handle Mismatches:
o If a mismatch occurs:
 If j is not 0, update j to lps[j - 1] to skip unnecessary comparisons.
 If j is 0, simply increment i.
 Continue Until End of Text:
Repeat the comparison until the end of the text is reached. Output the indices of
found matches.

CODE :

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void constructLps(string &pat, vector<int> &lps) {

int len = 0;
// lps[0] is always 0
lps[0] = 0;
int i = 1;
while (i < pat.length()) {
 69

if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
}

vector<int> search(string &pat, string &txt) {

int n = txt.length();
int m = pat.length();
vector<int> lps(m);
vector<int> res;
constructLps(pat, lps);
int i = 0;
int j = 0;
while (i < n) {
if (txt[i] == pat[j]) {
i++;
j++;
if (j == m) {
 70

res.push_back(i - j);
j = lps[j - 1];
}
}
else {
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
return res;
}

int main() {

string txt = "aabaacaadaabaaba";

string pat = "aaba";
cout <<"the patern was found at the following indexes :\n\n\t";
vector<int> res = search(pat, txt);
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";

return 0;
}
 71

OUTPUT :

Complexity :
 Time Complexity : O(n+m) , where (n) is the length of the target and (m) is the length of the search.

 Space Complexity : O(m) because of the pre-processing involved, such as creating the pi table for
the pattern.

..
 72

EXPERIMENT : 15
AIM : WAP to implement Sorting Network :
g(i,s) = min{Cik + g(k , S –{k})} .
 Compiler Requirement : Dev C++
 Algorithm :

 Initialize:
o Let nnn be the number of elements to be sorted.
o Create a cost matrix CCC, where C[i][k]C[i][k]C[i][k] represents the cost of
comparing the ithi^{th}ith and kthk^{th}kth elements.
 Recursive Function:
o Define a recursive function g(i,S)g(i, S)g(i,S) where SSS is the current set of
indices to sort. The function returns the minimum cost of sorting the elements
in SSS.

 Base Case:

o If SSS has only one element, the cost is 000 because it's already sorted.

 Recursive Case:

o For each element kkk in SSS, compute the cost of sorting the remaining
elements after comparing the ithi^{th}ith element with kkk and accumulate
the costs.

 Memoization:

o Store computed results in a table to avoid redundant calculations.

CODE :

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <unordered_map>

using namespace std;

 73

int g(int i, const vector<int>& S, const vector<vector<int>>& C,

unordered_map<string, int>& memo) {
// Base case: if the set is empty or has one element
if (S.size() <= 1) return 0;
// Create a unique key for memoization
string key = to_string(i) + ",";
for (int num : S) key += to_string(num) + ",";
if (memo.find(key) != memo.end()) return memo[key];
int minCost = INT_MAX;
for (int k : S) {
vector<int> newS(S);
newS.erase(remove(newS.begin(), newS.end(), k), newS.end());
// Calculate the cost
int cost = C[i][k] + g(k, newS, C, memo);
minCost = min(minCost, cost);
}

memo[key] = minCost; // Memoize the result

return minCost;
}

int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;

vector<vector<int>> C(n, vector<int>(n));

cout << "Enter the cost matrix (size " << n << "x" << n << "):\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> C[i][j];
 74

}
}

vector<int> S;
for (int i = 0; i < n; ++i) {
S.push_back(i);
}

unordered_map<string, int> memo; // Memoization map

int result = g(0, S, C, memo);

cout << "Minimum cost to sort the elements: " << result << endl;

return 0;
}

OUTPUT :

Complexity :
 Time Complexity : Worst-case: O(n⋅2n) in this case and generally it is : O(log n)

 Space Complexity : O(n⋅2n) in this case and generally it is : O(1).

 75

EXPERIMENT :
AIM : WAP to implement .
 Compiler Requirement : Dev C++
 Algorithm :
In .
 M

CODE :

OUTPUT :

Complexity :
 Time Complexity : hh

 Space Complexity : hh

..
(2nd last kr 3rd last )