Experiment-4

Aim: To perform Randomised Quick Sort using array as data structure and analyze its time
complexity.

#include <iostream>
#include <chrono>
#include <cstdlib>
#include <ctime>
using namespace std;
using namespace std::chrono;

int partition(int A[], int p, int r) {

int pivot = A[p];
int i = p;
int j = r + 1;
while (true) {
do { i++;}
while (i <= r && A[i] < pivot);
do { j--;}
while (A[j] > pivot);
if (i >= j) break;
swap(A[i], A[j]); }
swap(A[p], A[j]);
return j;}
int randomPartition(int A[], int p, int r) {
int i = p + rand() % (r - p + 1);
return partition(A, p, r); }
void randomizedQuicksort(int A[], int p, int r) {
if (p < r) {
int q = randomPartition(A, p, r);
randomizedQuicksort(A, p, q - 1);
 randomizedQuicksort(A, q + 1, r);
}}
void printArray(int A[], int size) {
for (int i = 0; i < size; i++) {
cout << A[i] << " ";}
cout << endl;}
int main() {
int Arr[50000],n;
cout << "Enter the size of Array : ";
cin >> n;
for (int i= 0; i<n; i++)
Arr[i] = rand()%n;
srand(time(0));
auto start = high_resolution_clock::now();
randomizedQuicksort(Arr, 0, n - 1);
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
cout << "Sorted array: ";
printArray(Arr, n);
cout << "Time taken by randomized quicksort: " << duration.count() << " microseconds"
<< endl;
cout << "\ CSE-1" << endl;
return 0;
}
 Experiment-5
Aim: To implement Matrix Multiplication using Strassen’s algorithm and analyse its time
complexity.

#include <iostream>

#include <chrono>

using namespace std;

using namespace std::chrono;

void add(int** A, int** B, int** C, int size) {

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

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

C[i][j] = A[i][j] + B[i][j];

}}}

void subtract(int** A, int** B, int** C, int size) {

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

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

C[i][j] = A[i][j] - B[i][j];

}}}

void strassen(int** A, int** B, int** C, int size) { // Strassen's Matrix Multiplication

if (size == 1) {

C[0][0] = A[0][0] * B[0][0];

return;

int newSize = size / 2;

int** A11 = new int*[newSize]; // Allocating memory for submatrices

int** A12 = new int*[newSize];

int** A21 = new int*[newSize];

int** A22 = new int*[newSize];

int** B11 = new int*[newSize];

int** B12 = new int*[newSize];

int** B21 = new int*[newSize];

int** B22 = new int*[newSize];

int** C11 = new int*[newSize];

int** C12 = new int*[newSize];

int** C21 = new int*[newSize];

int** C22 = new int*[newSize];

int** P1 = new int*[newSize];

int** P2 = new int*[newSize];

int** P3 = new int*[newSize];

int** P4 = new int*[newSize];

int** P5 = new int*[newSize];

int** P6 = new int*[newSize];

int** P7 = new int*[newSize];

int** tempA = new int*[newSize];

int** tempB = new int*[newSize];

for (int i = 0; i < newSize; i++) { // Initialize submatrices

A11[i] = new int[newSize];

A12[i] = new int[newSize];

A21[i] = new int[newSize];

A22[i] = new int[newSize];

 B11[i] = new int[newSize];

B12[i] = new int[newSize];

B21[i] = new int[newSize];

B22[i] = new int[newSize];

C11[i] = new int[newSize];

C12[i] = new int[newSize];

C21[i] = new int[newSize];

C22[i] = new int[newSize];

P1[i] = new int[newSize];

P2[i] = new int[newSize];

P3[i] = new int[newSize];

P4[i] = new int[newSize];

P5[i] = new int[newSize];

P6[i] = new int[newSize];

P7[i] = new int[newSize];

tempA[i] = new int[newSize];

tempB[i] = new 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];

} }

subtract(B12, B22, tempB, newSize);

strassen(A11, tempB, P1, newSize); // P1 = A11 * (B12 - B22)

add(A11, A12, tempA, newSize);

strassen(tempA, B22, P2, newSize); // P2 = (A11 + A12) * B22

add(A21, A22, tempA, newSize);

strassen(tempA, B11, P3, newSize); // P3 = (A21 + A22) * B11

subtract(B21, B11, tempB, newSize);

strassen(A22, tempB, P4, newSize); // P4 = A22 * (B21 - B11)

add(A11, A22, tempA, newSize);

add(B11, B22, tempB, newSize);

strassen(tempA, tempB, P5, newSize); // P5 = (A11 + A22) * (B11 + B22)

subtract(A12, A22, tempA, newSize);

add(B21, B22, tempB, newSize);

strassen(tempA, tempB, P6, newSize); // P6 = (A12 - A22) * (B21 + B22)

subtract(A11, A21, tempA, newSize);

add(B11, B12, tempB, newSize);

strassen(tempA, tempB, P7, newSize); // P7 = (A11 - A21) * (B11 + B12)

add(P5, P4, tempA, newSize); // Calculating C11, C12, C21, and C22

subtract(tempA, P2, tempB, newSize);

add(tempB, P6, C11, newSize);

add(P1, P2, C12, newSize);

 add(P3, P4, C21, newSize);

add(P5, P1, tempA, newSize);

subtract(tempA, P3, tempB, newSize);

subtract(tempB, P7, C22, newSize);

for (int i = 0; i < newSize; i++) { // Combining results into final matrix C

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

} }

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

delete[] A11[i]; delete[] A12[i]; delete[] A21[i]; delete[] A22[i];

delete[] B11[i]; delete[] B12[i]; delete[] B21[i]; delete[] B22[i];

delete[] C11[i]; delete[] C12[i]; delete[] C21[i]; delete[] C22[i];

delete[] P1[i]; delete[] P2[i]; delete[] P3[i]; delete[] P4[i];

delete[] P5[i]; delete[] P6[i]; delete[] P7[i]; delete[] tempA[i];

delete[] tempB[i];

delete[] A11; delete[] A12; delete[] A21; delete[] A22;

delete[] B11; delete[] B12; delete[] B21; delete[] B22;

delete[] C11; delete[] C12; delete[] C21; delete[] C22;

delete[] P1; delete[] P2; delete[] P3; delete[] P4; delete[] P5; delete[] P6; delete[] P7;

delete[] tempA; delete[] tempB;}

void printMatrix(int** matrix, int size) {

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

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

cout << matrix[i][j] << " ";

} cout << endl;

}}

int main() {

int n;

cout << "Enter matrix dimension (must be power of 2): ";

cin >> n;

int** A = new int*[n];

int** B = new int*[n];

int** C = new int*[n];

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

A[i] = new int[n];

B[i] = new int[n];

C[i] = new int[n];

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

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

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

cin >> A[i][j];

} }

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

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

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

 cin >> B[i][j];

} }

auto start = high_resolution_clock::now();

strassen(A, B, C, n); // Strassen's multiplication

auto end = high_resolution_clock::now();

auto duration = duration_cast<microseconds>(end - start);

cout << "\nResultant matrix C (A * B):\n";

printMatrix(C, n);

cout << "\nTime taken for Strassen's Matrix Multiplication: " << duration.count() << "
microseconds\n";

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

delete[] A[i];

delete[] B[i];

delete[] C[i];

delete[] A; delete[] B; delete[] C;

cout << "\n CSE-1" << endl;

return 0;}
 Experiment-6
Aim: To perform Fractional Knapsack using array as data structure and analyze its time
complexity.

#include <iostream>
#include <algorithm>
using namespace std;
struct Item {
int weight;
int value;
};
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;}
double fractionalKnapsack(int m, Item items[], int n) {
sort(items, items + n, cmp);
double totalValue = 0.0;
double x[100];
int U = m;
for (int i = 0; i < n; i++) {
x[i] = 0.0;}
for (int i = 0; i < n; i++) {
if (items[i].weight <= U) {
x[i] = 1.0;
totalValue += items[i].value;
U -= items[i].weight;
} else {
x[i] = (double)U / items[i].weight;
totalValue += x[i] * items[i].value;
break;}}
 cout << "Solution vector (fractions of items taken): ";
for (int i = 0; i < n; i++) {
cout << x[i] << " ";}
cout << endl;
return totalValue;
}
int main() {
int n, m;
cout << "Enter the number of items: ";
cin >> n;
Item items[n];
cout << "Enter the capacity of the knapsack: ";
cin >> m;
for (int i = 0; i < n; i++) {
cout << "Enter weight and value for item " << i + 1 << ": ";
cin >> items[i].weight >> items[i].value;}
double maxValue = fractionalKnapsack(m, items, n);
cout << "Maximum value in knapsack = " << maxValue;
cout << "\n CSE-1" << endl;
return 0;
}
 Experiment-7
Aim: To implement Binary Search using array as a data structure and analyse its time
complexity.

#include <iostream>

#include <chrono> // Include for measuring execution time

using namespace std;

using namespace std::chrono;

int binary_search(int arr[], int beg, int end, int x) { // Fn to perform binary search on a sorted
array

int mid; // Variable to hold the midpoint of the current search range

while (beg <= end) {

mid = (beg + end) / 2; // Calculate the midpoint

if (arr[mid] == x)

return mid; // Return the index if found

if (arr[mid] > x)

end = mid - 1; // Update end index to mid - 1

else

beg = mid + 1; // Search the right subarray

} return -1; // Return -1 if the element is not found

int main() {

int data[1000], n, i, result, item;

cout << "Enter the size of array: "; // Input the size of the array

cin >> n;

if (n > 1000) {cout << "Array size exceeds limit of 1000.\n";

return 1; // Exit with error if the size is too large

 }

cout << "Enter the elements of the array in sorted order: ";

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

cin >> data[i]; // Read each element

cout << "Enter the element you want to search in the given array: ";

cin >> item;

auto start = high_resolution_clock::now();

result = binary_search(data, 0, n - 1, item);

auto stop = high_resolution_clock::now();

auto duration = duration_cast<microseconds>(stop - start);

if (result == -1) {

cout << "The given element " << item << " is not present in the array." << endl;

} else {

cout << "Element " << item << " is present in the array at position " << result + 1 << "."
<< endl; }

cout << "Time taken by binary search: " << duration.count() << " microseconds" << endl;

cout << "\n CSE-1" << endl;

return 0;

}
 EXPERIMENT-9

 AIM : Write a program to implement Longest Common Sequence (LCS).

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

/* Utility function to get max of 2 integers */

int max(int a, int b) {
return (a > b) ? a : b;
}
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs(string X, string Y, int m, int n, int L[][100]) {
// Build the LCS length matrix in bottom-up fashion
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0; // First row and first column are all zeros
}
else if (X[i - 1] == Y[j - 1]) {
L[i][j] = L[i - 1][j - 1] + 1; // Characters match, add 1 to diagonal
}
else {
L[i][j] = max(L[i - 1][j], L[i][j - 1]); // Take the max from top or
left
} } }
cout << "LCS Length Matrix: \n";
for (int i = 0; i <= m; i++) {
 for (int j = 0; j <= n; j++) {
cout << L[i][j] << " ";
}
cout << endl;
}
return L[m][n]; // Length of LCS for X[0..m-1], Y[0..n-1]
}
/* Utility function to print the LCS string */
void printLCS(string X, string Y, int m, int n, int L[][100]) {
// We start from L[m][n] and trace back the LCS
int i = m, j = n;
string lcs_str = "";
while (i > 0 && j > 0) {
if (X[i - 1] == Y[j - 1]) {
lcs_str = X[i - 1] + lcs_str; // Add character to the result
i--;
j--;
} else if (L[i - 1][j] >= L[i][j - 1]) {
i--; // Move up
} else {
j--; // Move left
} }
cout << "Longest Common Subsequence: " << lcs_str << endl;
}
int main() {
string X, Y;
cout << "Enter first string : "; cin >> X ;
 cout << "Enter second string: "; cin >> Y ;
int m = X.length();
int n = Y.length();
// Initialize a matrix to store the length of LCS for all subproblems
int L[100][100]; // Assuming max length of X and Y is 100
// Compute LCS length and print the matrix
int lcsLength = lcs(X, Y, m, n, L);
// Output the final LCS length
cout << "\nLength of LCS is: " << lcsLength << endl;
// Print the actual LCS string
printLCS(X, Y, m, n, L);
return 0;
}
 EXPERIMENT- 8
 AIM : Write a program to implement Matrix Chain Multiplication (MCM).

 CODE :
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Function to perform Matrix Chain Multiplication
int matrixChainMultiplication(vector<int>& dims) {
int n = dims.size() - 1; // Number of matrices
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j +
1];
dp[i][j] = min(dp[i][j], cost);
} } }
return dp[0][n - 1];
}
int main() {
int n;
cout << "Enter the number of matrices: ";
cin >> n;
vector<int> dims(n + 1);
cout << "Enter the dimensions of matrices (as an array of size " << n + 1
<< "): ";
for (int i = 0; i <= n; i++) {
cin >> dims[i];
}
int minCost = matrixChainMultiplication(dims);
cout << "Minimum number of multiplications required: " << minCost <<
endl;
return 0;
}