GROUP - B

CODE:COR08P/08: Write a C++ program to find the minimum number of scalar multiplication needed
for the chain of matrix?

#include <iostream>
#include <climits>
using namespace std;
int matrixChainMultiplication(int dims[], int n) {
int dp[n][n];
for (int i = 1; i < n; i++) {
dp[i][i] = 0;
}
for (int length = 2; length < n; length++) {
for (int i = 1; i < n - length + 1; i++) {
int j = i + length - 1;
dp[i][j] = INT_MAX;
for (int k = i; k <= j - 1; k++) {
int cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j];
if (cost < dp[i][j]) {
dp[i][j] = cost;
}
}
}
}
return dp[1][n - 1];
}

int main() {
int n;
cout << "Enter the number of matrices: ";
cin >> n;
int dims[n + 1];
cout << "Enter the dimensions of the matrices: ";
for (int i = 0; i <= n; i++) {
cin >> dims[i];
}
cout << "Minimum number of scalar multiplications is " << matrixChainMultiplication(dims, n + 1);
return 0;
}

OUTPUT:
CODE:COR08P/09: Write a C++ program to find the LCS?

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

// Function to find the LCS of two strings

string findLCS(const string& X, const string& Y) {
int m = X.length();
int n = Y.length();
int dp[m + 1][n + 1];
// Initialize the dp table
memset(dp, 0, sizeof(dp));
// Build the dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X[i - 1] == Y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Reconstruct the LCS from the dp table
int index = dp[m][n];
char lcs[index + 1];
lcs[index] = '\0'; // Set the terminating character
int i = m, j = n;
while (i > 0 && j > 0) {
if (X[i - 1] == Y[j - 1]) {
lcs[--index] = X[i - 1];
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return string(lcs);
}

int main() {
string X, Y;
cout << "Enter the first string: ";
 cin >> X;
cout << "Enter the second string: ";
cin >> Y;
string lcs = findLCS(X, Y);
cout << "The Longest Common Subsequence is: " << lcs << endl;
return 0;
}

OUTPUT:
CODE:COR08P/10: Write a C++ program to find the profit on 0/1 Knapsack ?

#include <iostream>
#include <cstring>
using namespace std;
int knapsack(int W, int wt[], int val[], int n) {
int dp[n + 1][W + 1];
// Initialize the dp table
memset(dp, 0, sizeof(dp));
// Build the dp table
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (wt[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
int main() {
int n, W;
cout << "Enter the number of items: ";
cin >> n;
int val[n], wt[n];
cout << "Enter the values of the items: ";
for (int i = 0; i < n; i++) {
cin >> val[i];
}
cout << "Enter the weights of the items: ";
for (int i = 0; i < n; i++) {
cin >> wt[i];
}
cout << "Enter the capacity of the knapsack: ";
cin >> W;
cout << "The maximum profit is: " << knapsack(W, wt, val, n) << endl;
return 0;
}
OUTPUT:
CODE:COR08P/11: Write a C++ program to implement Factorial Knapsack problem?

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

// Function to calculate factorial

int factorial(int n) {
if (n == 0 || n == 1)
return 1;
int fact = 1;
for (int i = 2; i <= n; i++)
fact *= i;
return fact;
}

// Function to find the maximum profit for the 0/1 Knapsack problem
int knapsack(int W, int wt[], int val[], int n) {
int dp[n + 1][W + 1];
// Initialize the dp table
memset(dp, 0, sizeof(dp));
// Build the dp table
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (wt[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}

int main() {
int n, W;
cout << "Enter the number of items: ";
cin >> n;
int wt[n], val[n];
cout << "Enter the weights of the items: ";
for (int i = 0; i < n; i++) {
cin >> wt[i];
val[i] = factorial(i + 1); // Using factorial of the item's index as its value
}
cout << "Enter the capacity of the knapsack: ";
 cin >> W;
cout << "The maximum profit is: " << knapsack(W, wt, val, n) << endl;
return 0;
}

OUTPUT:
CODE:COR08P/12: Write a C++ program to implement Naïve Algorithm?

#include <iostream>
#include <string>

using namespace std;

// Function to implement the Naïve algorithm for pattern searching

void naiveSearch(const string& text, const string& pattern) {
int n = text.length();
int m = pattern.length();

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

int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
break;
}
}

if (j == m) {
cout << "Pattern found at index " << i << endl;
}
}
}

int main() {
string text, pattern;
cout << "Enter the text: ";
getline(cin, text);
cout << "Enter the pattern: ";
getline(cin, pattern);

naiveSearch(text, pattern);

return 0;
}

OUTPUT:
CODE:COR08P/13: Write a C++ program to implement string matching algorithm using KMP (Knuth-
Morris-Pratt) Algorithm?

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

// Function to compute the LPS (Longest Prefix Suffix) array

void computeLPSArray(const std::string& pattern, int* lps) {
int length = 0; // length of the previous longest prefix suffix
int i = 1;
lps[0] = 0; // lps[0] is always 0

// Loop to calculate lps[i] for i = 1 to M-1

while (i < pattern.length()) {
if (pattern[i] == pattern[length]) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}

// KMP search algorithm

void KMPSearch(const std::string& text, const std::string& pattern) {
int M = pattern.length();
int N = text.length();
// Create lps[] that will hold the longest prefix suffix values for the pattern
int* lps = new int[M];
computeLPSArray(pattern, lps);
int i = 0; // index for text[]
int j = 0; // index for pattern[]
while (i < N) {
if (pattern[j] == text[i]) {
i++;
j++;
}
 if (j == M) {
cout << "Found pattern at index " << i - j << endl;
j = lps[j - 1];
} else if (i < N && pattern[j] != text[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
delete[] lps; // Free the dynamically allocated memory
}

int main() {
string text;
string pattern;
cout << "Enter the text: ";
getline(cin, text);
cout << "Enter the pattern: ";
getline(cin, pattern);
KMPSearch(text, pattern);
return 0;
}

OUTPUT:
CODE:COR08P/14: Write a C++ program to implement single source shortest path for a graph using
Dijkstra Algorithm?

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

// Function to find the vertex with minimum distance value, from

// the set of vertices not yet included in the shortest path tree
int minDistance(int dist[], bool sptSet[], int V) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; ++v)
if (!sptSet[v] && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// Function to perform Dijkstra's Algorithm
void dijkstra(int** graph, int V, int src) {
int* dist = new int[V]; // Array to store the shortest distance from source to each vertex
bool* sptSet = new bool[V]; // Array to keep track of vertices included in the shortest path tree

// Initialize distances to all vertices as infinite and sptSet[] as false

for (int i = 0; i < V; ++i) {
dist[i] = INT_MAX;
sptSet[i] = false;
}
// Distance to the source is 0
dist[src] = 0;
for (int count = 0; count < V - 1; ++count) {
// Pick the minimum distance vertex from the set of vertices not yet processed
int u = minDistance(dist, sptSet, V);
sptSet[u] = true;
// Update dist[] value of the adjacent vertices of the picked vertex
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];
}
// Print shortest distances from source
cout << "Vertex Distance from Source" << endl;
for (int i = 0; i < V; ++i)
cout << i << "\t\t" << dist[i] << endl;
delete[] dist;
delete[] sptSet;
}
int main() {
int V = 5; // Number of vertices
int E = 6; // Number of edges
// Dynamically allocate a 2D array for the graph
int** graph = new int*[V];
for (int i = 0; i < V; ++i) {
graph[i] = new int[V];
for (int j = 0; j < V; ++j)
graph[i][j] = 0; // Initialize the graph with 0s (no edges)
}
// Initialize graph with edges and weights
int edges[E][3] = {
{0, 1, 10},
{0, 4, 5},
{1, 2, 1},
{1, 4, 2},
{2, 3, 4},
{3, 4, 9}
};
for (int i = 0; i < E; ++i) {
int u = edges[i][0];
int v = edges[i][1];
int w = edges[i][2];
graph[u][v] = w;
graph[v][u] = w; // Comment this line if the graph is directed
}
int src = 0; // Source vertex
dijkstra(graph, V, src);
// Deallocate the 2D array
for (int i = 0; i < V; ++i)
delete[] graph[i];
delete[] graph;
return 0;
}

OUTPUT:
CODE:COR08P/15: Write a C++ program to implement single source shortest path for a graph using
Bellman Ford Algorithm?

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

// Struct to represent an edge in the graph

struct Edge {
int source, destination, weight;
};

// Function to perform Bellman-Ford algorithm

void bellmanFord(vector<Edge> &edges, int V, int source) {
// Initialize distances from source to all vertices as INFINITE
vector<int> distance(V, numeric_limits<int>::max());
distance[source] = 0;

// Relax all edges V-1 times

for (int i = 1; i <= V - 1; ++i) {
for (const auto &edge : edges) {
int u = edge.source;
int v = edge.destination;
int weight = edge.weight;
if (distance[u] != numeric_limits<int>::max() &&
distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
}
}
}

// Check for negative-weight cycles

for (const auto &edge : edges) {
int u = edge.source;
int v = edge.destination;
int weight = edge.weight;
if (distance[u] != numeric_limits<int>::max() &&
distance[u] + weight < distance[v]) {
cout << "Graph contains negative weight cycle\n";
return;
}
}
 // Print distances
cout << "Vertex Distance from Source:\n";
for (int i = 0; i < V; ++i) {
cout << i << "\t\t" << distance[i] << "\n";
}
}

// Driver code
int main() {
// Example graph representation
vector<Edge> edges = {{0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2},
{1, 4, 2}, {3, 2, 5}, {3, 1, 1}, {4, 3, -3}};
int V = 5; // Number of vertices in graph
int source = 0; // Source vertex

bellmanFord(edges, V, source);

return 0;
}

OUTPUT:
CODE:COR08P/16: Write a C++ program to implement single source shortest path for a graph using
Floyed Warshall Algorithm?

#include <iostream>
#include <limits>
#include <vector>

using namespace std;

#define INF numeric_limits<int>::max()

// Function to perform Floyd-Warshall algorithm

void floydWarshall(vector<vector<int>> &graph, int V) {
// Initialize distances matrix with graph weights
vector<vector<int>> dist(graph);

// Apply Floyd-Warshall algorithm

for (int k = 0; k < V; ++k) {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
// If vertex k is on the shortest path from i to j,
// then update the value of dist[i][j]
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}

// Print the shortest distances

cout << "Shortest distances between every pair of vertices:\n";
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
if (dist[i][j] == INF) {
cout << "INF\t";
} else {
cout << dist[i][j] << "\t";
}
}
cout << "\n";
}
}
// Driver code
int main() {
// Example graph representation
int V = 4; // Number of vertices in graph
vector<vector<int>> graph = {
{0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF, 0}};

floydWarshall(graph, V);

return 0;
}

OUTPUT:
 GROUP - A
Assignment No. Description Page No. Signature

COR08P/01 WAP in C++ to implement Binary Search 01-02

COR08P/02 WAP in C++ to implement Insertion Sort 03-04

COR08P/03 WAP in C++ to implement Quick Sort 05-06

COR08P/04 WAP in C++ to implement Merge Sort 07-08

COR08P/05 WAP in C++ to implement Heap Sort 09-10

COR08P/06 WAP in C++ to implement Count Sort 11-12

COR08P/07 WAP in C++ to implement Radix Sort 13-14

GROUP – B
Assignment No. Description Page No. Signature

COR08P/08 WAP in C++ to find the minimum number of scalar 15

multiplication needed for the chain of matrix
COR08P/09 WAP in C++ to find the LCS 16-17

COR08P/10 WAP in C++ to find the profit on 0/1 Knapsack 18

COR08P/11 WAP in C++ to implement Factorial Knapsack problem 19-20

COR08P/12 WAP in C++ to implement Naïve Algorithm 21

COR08P/13 WAP in C++ to implement string matching algorithm 22-23

using KMP(Knuth-Morris-Pratt) Algorithm
COR08P/14 WAP in C++ to implement single source shortest path 24-25
for a graph using Dijkstra Algorithm
COR08P/15 WAP in C++ to implement single source shortest path 26-27
for a graph using Bellman Ford Algorithm
COR08P/16 WAP in C++ to implement single source shortest path 28-29
for a graph using Floyed Warshall Algorithm