GROUP – B

ASSIGNMENT 1 :
Q. Find the minimum number of scalar multiplication needed for
chain of matrix.
SOURCE CODE :
#include <iostream>
#include <limits.h>
int minScalarMultiplications(int dimensions[], int n) {
int dp[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = 0;
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + dimensions[i] * dimensions[k + 1] *
dimensions[j + 1];
dp[i][j] = (dp[i][j] < cost) ? dp[i][j] : cost;
}
}
}
return dp[0][n - 1];
}
int main() {

[Date] 18
 int n;
std::cout << "Enter the number of matrices: ";
std::cin >> n;
int dimensions[n + 1];
std::cout << "Enter the dimensions of the matrices: ";
for (int i = 0; i <= n; i++) {
std::cin >> dimensions[i];
}
int minMultiplications = minScalarMultiplications(dimensions, n);
std::cout << "Minimum number of scalar multiplications: " <<
minMultiplications << std::endl;
return 0;
}

OUTPUT :

[Date] 19
ASSIGNMENT 2 :
Q. Find the LCS.
SOURCE CODE :
#include<iostream>

using namespace std;

int lcs(string x,string y,int m,int n) {

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

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

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

if(i==0||j==0)

L[i][j]=0;

else if(x[i-1]==y[j-1])

L[i][j]=L[i-1][j-1]+1;

else

L[i][j]=max(L[i-1][j],L[i][j-1]);

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

cout<<endl;

int len=L[m][n];

string sub_string="";

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

sub_string+='$';

int i=m,j=n,index=len-1;

while(i>0 && j>0){

if(x[i-1]==y[j-1]){

sub_string[index]=y[j-1];

index--;

i--;

j--;

[Date] 20
 }

else if(L[i-1][j]>L[i][j-1])

j--;

else

i--;

cout<<sub_string<<endl;

cout<<"Longest Common sequence is: "<<sub_string<<endl;

return L[m][n];

int main(){

string s1="ABCBDAB";

string s2="BDCABA";

int m=s1.size();

int n=s2.size();

int res=lcs(s1,s2,m,n);

cout<<"Length of LCS is: "<<res;

return 0;

OUTPUT :

[Date] 21
ASSIGNMENT 3:
Q. Find the Profit on Zero-one Knapsack.
SOURCE CODE :
#include<iostream>
#include<algorithm>
using namespace std;
int Knapsack(int weight[],int w,int value[],int v){
int knap[w+1][v+1];
for(int i=0;i<=v;i++){
for(int j=0;j<=w;j++){
int weigh=j-weight[i];
if(i==0||j==0){
knap[i][j]=0;
}
else if(weigh>=0){
knap[i][j]=max(knap[i-1][j],value[i]+knap[i-1][weigh]);
}
else{
knap[i][j]=knap[i-1][j];
}
}
}
for(int i=0;i<=v;i++){
for(int j=0;j<=w;j++){
cout<<knap[i][j]<<" ";
}
cout<<endl;

[Date] 22
 }
return knap[w][v];
}
int main(){
int weight[]={2,1,3,2};
int value[]={12,10,20,15};
int w=sizeof(weight)/sizeof(weight[0]);
int v=sizeof(value)/sizeof(value[0]);
cout<<"knapsack table:"<<endl;
int maxValue=Knapsack(weight,w,value,v);
cout<<"max value: "<<maxValue;
return 0;
}

OUTPUT :

[Date] 23
ASSIGNMENT 4:
Q. Implement Fractional Knapsack Problem.
SOURCE CODE :
#include <iostream>

using namespace std;

double fractionalKnapsack(int capacity, int values[], int weights[], int n) {

double maxValue = 0.0;

double valuePerWeight[n];

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

valuePerWeight[i] = (double)values[i] / (double)weights[i];

while (capacity > 0) {

int maxIndex = -1;

double maxValPerWeight = 0.0;

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

if (weights[i] > 0 && valuePerWeight[i] > maxValPerWeight) {

maxValPerWeight = valuePerWeight[i];

maxIndex = i;

if (maxIndex == -1)

break; // No more items can be added to the knapsack

if (weights[maxIndex] <= capacity) {

maxValue += values[maxIndex];

capacity -= weights[maxIndex];

weights[maxIndex] = 0; // Mark the item as taken

} else {

maxValue += (valuePerWeight[maxIndex] * capacity);

capacity = 0;

return maxValue;

[Date] 24
int main() {

int capacity;

cout << "Enter the capacity of the knapsack: ";

cin >> capacity;

int n;

cout << "Enter the number of items: ";

cin >> n;

int values[n];

int weights[n];

cout << "Enter the value of each item:\n";

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

cin >> values[i];

cout << "Enter the weight of each item:\n";

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

cin >> weights[i];

double maxValue = fractionalKnapsack(capacity, values, weights, n);

cout << "Maximum value that can be obtained: " << maxValue << endl;

return 0;

OUTPUT :

[Date] 25
ASSISGNMENT 5 :

Q. Implement all pair of Shortest path for a graph(Floyed-Warshall Algorithm).

SOURCE CODE :
#include <iostream>
#include <climits>
using namespace std;
const int INF = INT_MAX;
const int V = 4;
void floydWarshall(int graph[V][V]) {
int dist[V][V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; 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];
}
}
}
}
cout << "The following matrix shows the 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 ";
} else {
cout << dist[i][j] << " ";
}
}
[Date]

cout << endl;

}
26
}
int main() {
int graph[V][V] = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(graph);
return 0;
}

OUTPUT:

[Date]

27
ASSISGNMENT 6 :

Q. Implement Single Source shortest path for a graph using

(i) Dijkstra Algorithm , (ii) Bellman Ford Algorithm

SOURCE CODE :
#include <iostream>
#include <climits>
using namespace std;
class Graph {
int V;
int **adjMatrix;
public:
Graph(int V) {
this->V = V;
adjMatrix = new int*[V];
for (int i = 0; i < V; i++) {
adjMatrix[i] = new int[V];
for (int j = 0; j < V; j++) {
adjMatrix[i][j] = (i == j) ? 0 : INT_MAX;
}
}
}
void addEdge(int u, int v, int w) {
adjMatrix[u][v] = w;
}
void dijkstra(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] && adjMatrix[u][v] != INT_MAX && dist[u] != INT_MAX
&& dist[u] + adjMatrix[u][v] < dist[v]) {
dist[v] = dist[u] + adjMatrix[u][v];
}
}
}
printSolution(dist);
}
void bellmanFord(int src) {
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
[Date]

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

for (int u = 0; u < V; u++) {

28
 for (int v = 0; v < V; v++) {
if (adjMatrix[u][v] != INT_MAX && dist[u] != INT_MAX
&& dist[u] + adjMatrix[u][v] < dist[v]) {

dist[v] = dist[u] + adjMatrix[u][v];

}
}
}
}
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++) {
if (adjMatrix[u][v] != INT_MAX && dist[u] != INT_MAX
&& dist[u] + adjMatrix[u][v] < dist[v]) {
cout << "Graph contains negative weight cycle\n";
return;
}
}
}
printSolution(dist);
}
private:
int minDistance(int dist[], bool sptSet[]) {
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;
}
void printSolution(int dist[]) {
cout << "Vertex\tDistance from Source\n";
for (int i = 0; i < V; i++) {
cout << i << "\t\t" << dist[i] << "\n";
}
}
};
int main() {
int V, E, u, v, w, src;
cout << "Enter the number of vertices: ";
cin >> V;
Graph g(V);
cout << "Enter the number of edges: ";
cin >> E;
for (int i = 0; i < E; i++) {
cout << "Enter edge (u v w): ";
cin >> u >> v >> w;
g.addEdge(u, v, w);
[Date]

}
cout << "Enter the source vertex: ";
cin >> src;
29
 cout << "\nDijkstra's Algorithm:\n";

g.dijkstra(src);
cout << "\nBellman-Ford Algorithm:\n";
g.bellmanFord(src);
return 0; }

OUTPUT:

[Date]

30
ASSISGNMENT 7 :

Q. Implement String Matching Algorithm

(i) Navies’s Algorithm , (ii) KMP Algorithm .

SOURCE CODE :
#include <iostream>
#include <cstring>

class StringMatcher {
public:
void naiveSearch(const char* text, const char* pattern) {
int n = std::strlen(text);
int m = std::strlen(pattern);
int count = 0;

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) {
std::cout << "Pattern found at index " << i << std::endl;
count++;
}
}

if (count == 0) {
std::cout << "Pattern not found!" << std::endl;
} else {
std::cout << "Total occurrences: " << count << std::endl;
}
}

void KMPSearch(const char* text, const char* pattern) {

int n = std::strlen(text);
int m = std::strlen(pattern);
int* lps = new int[m];
int count = 0;

computeLPSArray(pattern, m, lps);

int i = 0; // index for text[]

int j = 0; // index for pattern[]
while (i < n) {
if (pattern[j] == text[i]) {
j++;
i++;
[Date]

31
 if (j == m) {
std::cout << "Pattern found at index " << i - j << std::endl;
count++;
j = lps[j - 1];
}
else if (i < n && pattern[j] != text[i]) {
if (j != 0) {
j = lps[j - 1];
}
else {
i++;
}
}
}

if (count == 0) {
std::cout << "Pattern not found!" << std::endl;
} else {
std::cout << "Total occurrences: " << count << std::endl;
}
delete[] lps;
}
private:
void computeLPSArray(const char* pattern, int m, int* lps) {
int length = 0;
lps[0] = 0;

int i = 1;
while (i < m) {
if (pattern[i] == pattern[length]) {
length++;
lps[i] = length;
i++;
}
else {
if (length != 0) {
length = lps[length - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
}
};
int main() {
char text[1000];
char pattern[100];
std::cout << "Enter the text: ";
[Date]

std::cin.getline(text, 1000);
std::cout << "Enter the pattern: ";
std::cin.getline(pattern, 100);
32
 StringMatcher sm;
std::cout << "\nNaive String Matching:" << std::endl;
sm.naiveSearch(text, pattern);

std::cout << "\nKMP String Matching:" << std::endl; sm.KMPSearch(text, pattern);

return 0;}

OUTPUT:

[Date]

33