Demystifying Algorithms & Solving Problems
In this blog post, you will find solutions for the lab component Analysis & Design of Algorithms Lab (BCDL404) course work for the IV semester of VTU university. The solutions to the lab component are coded in C/C++. We recommend using the Code:Blocks as the integrated development environment (IDE). You can find the lab syllabus on the university’s website or click below.
After getting the necessary development environment setup, Now lets focus on the solutions. Click on the appropriate hyperlink to go to your program of choice.
- Kruskal’s Algorithm
- Prim’s Algorithm
- Dynamic Programming
- Dijkstra’s Algorithm
- Topological Ordering of vertices in a DAG
- 0/1 Knapsack problem – Dynamic Programming
- Knapsack problem using Greedy method.
- Subset Sum Problem
- Selection Sort
- Quick Sort
- Merge Sort
- N Queen’s problem using Backtracking.
- Additional solutions
Program 01
Kruskal’s Algorithm
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal’s algorithm.
C++ Code
/******************************************************************************
*File : 01Kruskal.cpp
*Description : Program to find Minimum Cost Spanning Tree of a given
* undirected graph using Kruskal's algorithm.
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <iostream>
using namespace std;
const int MAXNODES = 10;
const int INF = 9999;
// Structure to represent an edge
struct edge
{
int u, v, cost;
};
int fnFindParent(int v, int parent[]);
void fnUnion_ij(int i, int j, int parent[]);
void fnInputGraph(int m, edge e[]);
int fnGetMinEdge(edge e[], int n);
void fnKruskal(int n, edge e[], int m);
/******************************************************************************
*Function : main
*Input parameters:
* int argc - no of commamd line arguments
*
char **argv - vector to store command line argumennts
*RETURNS : 0 on success
******************************************************************************/
int main( int argc, char **argv)
{
int n = 6, m = 20;
edge e[2*MAXNODES] = {{0,1,6},{1,4,4},{4,5,6},{5,3,2},{3,0,5},{0,2,1},
{1,2,5},{3,2,2},{4,2,6},{5,2,3} };
cout << "Enter the number of nodes : ";
cin >> n;
cout << "Enter the number of edges : ";
cin >> m;
// fnInputGraph(m, e);
fnKruskal(n, e, m);
return 0;
}
/******************************************************************************
*Function : fnFindParent
*Description : Function to find parent of a given vertex
*Input parameters:
* int v - vertex for whom parent has to be found
* int parent[] - parent vector
*RETURNS : parent vertex
******************************************************************************/
int fnFindParent(int v, int parent[])
{
while (parent[v] != v)
v = parent[v];
return v;
}
/******************************************************************************
*Function : fnUnion_ij
*Description : Function to merge two trees
*Input parameters:
* int i, j - vertices to be merged
* int parent[] - parent vector
*RETURNS : no value
******************************************************************************/
void fnUnion_ij(int i, int j, int parent[])
{
if(i < j)
parent[j] = i;
else
parent[i] = j;
}
/******************************************************************************
*Function : fnInputGraph
*Description : Function to read a graph
*Input parameters:
* int m - no of edges in the graph
* edge e[] - set of edges in the graph
*RETURNS : no value
******************************************************************************/
void fnInputGraph(int m, edge e[])
{
int i, j, k, cost;
for(k=0; k<m; k++)
{
cout << "Enter edge and cost in the form u, v, w : \n";
cin >> i >> j >> cost;
e[k].u = i;
e[k].v = j;
e[k].cost = cost;
}
}
/******************************************************************************
*Function : fnGetMinEdge
*Description : Function to find the least cost edge in the edge set
*Input parameters:
* edge e[] - set of edges in the graph
* int n - no of vertices in the graph
*RETURNS : index of least cost edge in the edge set
******************************************************************************/
int fnGetMinEdge(edge e[], int n)
{
int i, small, pos;
small = INF;
pos = -1;
for(i=0; i<n; i++)
{
if(e[i].cost < small)
{
small = e[i].cost;
pos = i;
}
}
return pos;
}
/******************************************************************************
*Function : fnKruskal
*Description : Function to find MST of a graph
*Input parameters:
* int n - no of vertices in the graph
* int m - no of edges in the graph
* edge e[] - set of edges in the graph
*RETURNS : no value
******************************************************************************/
void fnKruskal(int n, edge e[], int m)
{
int i, j, count, k, sum, u, v, t[MAXNODES][2], pos;
int parent[MAXNODES];
count = 0;
k = 0;
sum = 0;
for(i=0; i<n; i++)
{
parent[i] = i;
}
while(count != n-1)
{
pos = fnGetMinEdge(e,m);
if(pos == -1)
{
break;
}
u = e[pos].u;
v = e[pos].v;
i = fnFindParent(u,parent);
j = fnFindParent(v,parent);
if(i != j)
{
t[k][0] = u;
t[k][1] = v;
k++;
count++;
sum += e[pos].cost;
fnUnion_ij(i, j, parent);
}
e[pos].cost = INF;
}
if(count == n-1)
{
cout << "\nSpanning tree exists";
cout << "\nThe Spanning tree is shown below\n";
for(i=0; i<n-1; i++)
cout << t[i][0] << " " << t[i][1] << endl;
cout << "\nCost of the spanning tree : " << sum << endl;
}
else
cout << "\nThe spanning tree does not exist" << endl;
}C Code
/******************************************************************************
*File : 01Kruskal.c
*Description : Program to find Minimum Cost Spanning Tree of a given
* undirected graph using Kruskal's algorithm.
*Author : Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
const int MAXNODES = 10;
const int INF = 9999;
// Structure to represent an edge
typedef struct
{
int u, v, cost;
}edge;
int fnFindParent(int v, int parent[]);
void fnUnion_ij(int i, int j, int parent[]);
void fnInputGraph(int m, edge e[]);
int fnGetMinEdge(edge e[], int n);
void fnKruskal(int n, edge e[], int m);
/******************************************************************************
*Function : main
*Input parameters:
* int argc - no of commamd line arguments
*
char **argv - vector to store command line argumennts
*RETURNS : 0 on success
******************************************************************************/
int main( int argc, char **argv)
{
int n = 6, m = 20;
edge e[2*MAXNODES]; //sample graph {{0,1,6},{1,4,4},{4,5,6},{5,3,2},{3,0,5},{0,2,1},{1,2,5},{3,2,2},{4,2,6},{5,2,3} };
printf("Enter the number of nodes : ");
scanf("%d", &n);
printf("Enter the number of edges : ");
scanf("%d", &m);
fnInputGraph(m, e);
fnKruskal(n, e, m);
return 0;
}
/******************************************************************************
*Function : fnFindParent
*Description : Function to find parent of a given vertex
*Input parameters:
* int v - vertex for whom parent has to be found
* int parent[] - parent vector
*RETURNS : parent vertex
******************************************************************************/
int fnFindParent(int v, int parent[])
{
while (parent[v] != v)
v = parent[v];
return v;
}
/******************************************************************************
*Function : fnUnion_ij
*Description : Function to merge two trees
*Input parameters:
* int i, j - vertices to be merged
* int parent[] - parent vector
*RETURNS : no value
******************************************************************************/
void fnUnion_ij(int i, int j, int parent[])
{
if(i < j)
parent[j] = i;
else
parent[i] = j;
}
/******************************************************************************
*Function : fnInputGraph
*Description : Function to read a graph
*Input parameters:
* int m - no of edges in the graph
* edge e[] - set of edges in the graph
*RETURNS : no value
******************************************************************************/
void fnInputGraph(int m, edge e[])
{
int i, j, k, cost;
for(k=0; k<m; k++)
{
printf("Enter edge and cost in the form u, v, w : \n");
scanf("%d%d%d", &i, &j, &cost);
e[k].u = i;
e[k].v = j;
e[k].cost = cost;
}
}
/******************************************************************************
*Function : fnGetMinEdge
*Description : Function to find the least cost edge in the edge set
*Input parameters:
* edge e[] - set of edges in the graph
* int n - no of vertices in the graph
*RETURNS : index of least cost edge in the edge set
******************************************************************************/
int fnGetMinEdge(edge e[], int n)
{
int i, small, pos;
small = INF;
pos = -1;
for(i=0; i<n; i++)
{
if(e[i].cost < small)
{
small = e[i].cost;
pos = i;
}
}
return pos;
}
/******************************************************************************
*Function : fnKruskal
*Description : Function to find MST of a graph
*Input parameters:
* int n - no of vertices in the graph
* int m - no of edges in the graph
* edge e[] - set of edges in the graph
*RETURNS : no value
******************************************************************************/
void fnKruskal(int n, edge e[], int m)
{
int i, j, count, k, sum, u, v, t[MAXNODES][2], pos;
int parent[MAXNODES];
count = 0;
k = 0;
sum = 0;
for(i=0; i<n; i++)
{
parent[i] = i;
}
while(count != n-1)
{
pos = fnGetMinEdge(e,m);
if(pos == -1)
{
break;
}
u = e[pos].u;
v = e[pos].v;
i = fnFindParent(u,parent);
j = fnFindParent(v,parent);
if(i != j)
{
t[k][0] = u;
t[k][1] = v;
k++;
count++;
sum += e[pos].cost;
fnUnion_ij(i, j, parent);
}
e[pos].cost = INF;
}
if(count == n-1)
{
printf("\nSpanning tree exists");
printf("\nThe Spanning tree is shown below\n");
for(i=0; i<n-1; i++)
printf("%d %d\n",t[i][0], t[i][1]);
printf("\nCost of the spanning tree : %d\n", sum);
}
else
printf("\nThe spanning tree does not exist\n");
}Input Graph
For this program lets consider the following graph
Output
Enter the number of nodes : 6
Enter the number of edges : 10
Enter edge and cost in the form u, v, w :
0 1 6
Enter edge and cost in the form u, v, w :
1 4 4
Enter edge and cost in the form u, v, w :
4 5 6
Enter edge and cost in the form u, v, w :
5 3 2
Enter edge and cost in the form u, v, w :
3 0 5
Enter edge and cost in the form u, v, w :
0 2 1
Enter edge and cost in the form u, v, w :
1 2 5
Enter edge and cost in the form u, v, w :
3 2 2
Enter edge and cost in the form u, v, w :
4 2 6
Enter edge and cost in the form u, v, w :
5 2 3
Spanning tree exists
The Spanning tree is shown below
0 2
5 3
3 2
1 4
1 2
Cost of the spanning tree : 14
Spanning Tree of the graph
Program 02
Prim’s Algorithm
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Prim’s algorithm.
C++ Code
/******************************************************************************
*File : 02PrimMST.cpp
*Description: Program to find Minimum Cost Spanning Tree of a given
* undirected graph using Prim's algorithm.
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <iostream>
using namespace std;
const int MAXNODES = 10;
void fnPrims(int n, int cost[MAXNODES][MAXNODES]);
void fnGetMatrix(int n,int a[MAXNODES][MAXNODES]);
/******************************************************************************
*Function : main
*Input parameters:
* int argc - no of commamd line arguments
* char **argv - vector to store command line argumennts
*RETURNS : 0 on success
******************************************************************************/
int main( int argc, char **argv)
{
int a[MAXNODES][MAXNODES] = {
{0, 3, 9999, 7, 9}, {3, 0, 4, 2, 9999}, {9999, 4, 0, 5, 6},
{7, 2, 5, 0, 4}, {9, 9999, 6, 4, 0}};
int n = 5;
cout << "Enter the number of vertices : ";
cin >> n;
fnGetMatrix(n,a);
fnPrims(n,a);
return 0;
}
/******************************************************************************
*Function : fnPrims
*Description : Function to find Minimum Cost Spanning Tree of a given
* undirected graph using Prims algorithm.
*Input parameters:
* int n - no of vertices in the graph
* int cost[][] - cost adjacency matrix of the graph
*RETURNS : no value
******************************************************************************/
void fnPrims(int n, int cost[MAXNODES][MAXNODES])
{
int i, j, u, v, min;
int sum, k, t[MAXNODES][2], p[MAXNODES], d[MAXNODES], s[MAXNODES];
int source, count;
min = 9999;
source = 0;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(cost[i][j] != 0 && cost[i][j] <= min)
{
min = cost[i][j];
source = i;
}
}
}
for(i=0; i<n; i++)
{
d[i] = cost[source][i];
s[i] = 0;
p[i] = source;
}
s[source] = 1;
sum = 0;
k = 0;
count = 0;
while (count != n-1)
{
min = 9999;
u = -1;
for(j=0; j<n; j++)
{
if(s[j] == 0)
{
if(d[j] <= min)
{
min = d[j];
u = j;
}
}
}
t[k][0] = u;
t[k][1] = p[u];
k++;
count++;
sum += cost[u][p[u]];
s[u] = 1;
for(v=0; v<n; v++)
{
if(s[v]==0 && cost[u][v]<d[v])
{
d[v] = cost[u][v];
p[v] = u;
}
}
}
if(sum >= 9999)
cout << "nSpanning tree does not existn";
else
{
cout << "nThe spanning tree exists and minimum cost spanning tree is n";
for(i=0; i<k; i++)
cout << t[i][1] << " " << t[i][0] << endl;
cout << "nThe cost of the minimum cost spanning tree is " << sum << endl;
}
}
/******************************************************************************
*Function : fnGetMatrix
*Description : Function to read cost adjacency matrix of the graph
*Input parameters:
* int n - no of vertices in the graph
* int a[][] - cost adjacency matrix of the graph
*RETURNS : no value
******************************************************************************/
void fnGetMatrix(int n,int a[MAXNODES][MAXNODES])
{
int i, j;
cout << "Enter the Cost Adjacency Matrix" << endl;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
cin >> a[i][j];
}C Code
/******************************************************************************
*File : 02PrimMST.c
*Description: Program to find Minimum Cost Spanning Tree of a given
* undirected graph using Prim's algorithm.
*Author : Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
const int MAXNODES = 10;
void fnPrims(int n, int cost[MAXNODES][MAXNODES]);
void fnGetMatrix(int n,int a[MAXNODES][MAXNODES]);
/******************************************************************************
*Function : main
*Input parameters:
* int argc - no of commamd line arguments
* char **argv - vector to store command line argumennts
*RETURNS : 0 on success
******************************************************************************/
int main( int argc, char **argv)
{
int a[MAXNODES][MAXNODES];// sample graph = {{0, 3, 9999, 7, 9}, {3, 0, 4, 2, 9999}, {9999, 4, 0, 5, 6}, {7, 2, 5, 0, 4}, {9, 9999, 6, 4, 0}};
int n = 5;
printf("Enter the number of vertices : ");
scanf("%d", &n);
fnGetMatrix(n,a);
fnPrims(n,a);
return 0;
}
/******************************************************************************
*Function : fnPrims
*Description : Function to find Minimum Cost Spanning Tree of a given
* undirected graph using Prims algorithm.
*Input parameters:
* int n - no of vertices in the graph
* int cost[][] - cost adjacency matrix of the graph
*RETURNS : no value
******************************************************************************/
void fnPrims(int n, int cost[MAXNODES][MAXNODES])
{
int i, j, u, v, min;
int sum, k, t[MAXNODES][2], p[MAXNODES], d[MAXNODES], s[MAXNODES];
int source, count;
min = 9999;
source = 0;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
if(cost[i][j] != 0 && cost[i][j] <= min)
{
min = cost[i][j];
source = i;
}
}
}
for(i=0; i<n; i++)
{
d[i] = cost[source][i];
s[i] = 0;
p[i] = source;
}
s[source] = 1;
sum = 0;
k = 0;
count = 0;
while (count != n-1)
{
min = 9999;
u = -1;
for(j=0; j<n; j++)
{
if(s[j] == 0)
{
if(d[j] <= min)
{
min = d[j];
u = j;
}
}
}
t[k][0] = u;
t[k][1] = p[u];
k++;
count++;
sum += cost[u][p[u]];
s[u] = 1;
for(v=0; v<n; v++)
{
if(s[v]==0 && cost[u][v]<d[v])
{
d[v] = cost[u][v];
p[v] = u;
}
}
}
if(sum >= 9999)
printf("\nSpanning tree does not exist\n");
else
{
printf("\nThe spanning tree exists and minimum cost spanning tree is \n");
for(i=0; i<k; i++)
printf("%d %d\n",t[i][1], t[i][0]);
printf("\nThe cost of the minimum cost spanning tree is %d\n", sum);
}
}
/******************************************************************************
*Function : fnGetMatrix
*Description : Function to read cost adjacency matrix of the graph
*Input parameters:
* int n - no of vertices in the graph
* int a[][] - cost adjacency matrix of the graph
*RETURNS : no value
******************************************************************************/
void fnGetMatrix(int n,int a[MAXNODES][MAXNODES])
{
int i, j;
printf("Enter the Cost Adjacency Matrix\n");
for(i=0; i<n; i++)
for(j=0; j<n; j++)
scanf("%d", &a[i][j]);
}Input Graph
For this program lets consider the following graph
Output
Enter the number of vertices : 5
Enter the Cost Adjacency Matrix
0 3 9999 7 9
3 0 4 2 9999
9999 4 0 5 6
7 2 5 0 4
9 9999 6 4 0
The spanning tree exists and minimum cost spanning tree is
3 1
1 0
3 4
1 2
The cost of the minimum cost spanning tree is 13
Spanning Tree of the graph
Program 03
Floyd’s Algorithm
Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd’s algorithm.
C++ Code
/***************************************************************************
*File : 03AFloyd.cpp
*Description: Program to implement Floyd's Algorithm
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
***************************************************************************/
#include <iostream>
using namespace std;
/******************************************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************************************/
int main(void)
{
int iN, i, j, k;
int iaFloyd[10][10], iaCost[10][10];
cout << "n*********************************************************";
cout << "n*tPROGRAM TO IMPLEMENT FLOYD'S ALGORITHMt*n";
cout << "*********************************************************";
cout << "nEnter the number of verticesn";
cin >> iN;
cout << "nEnter the Cost adjacency Matrixn";
for(i=0;i<iN;i++)
for(j=0;j<iN;j++)
cin >> iaCost[i][j];
cout << "nInput Graphn";
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
cout << iaCost[i][j] << "t";
}
cout << endl;
}
cout << endl;
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
iaFloyd[i][j] = iaCost[i][j];
}
}
for(k=0;k<iN;k++)
{
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
if(iaFloyd[i][j] > (iaFloyd[i][k] + iaFloyd[k][j]))
iaFloyd[i][j] = (iaFloyd[i][k] + iaFloyd[k][j]);
}
}
}
cout << "nAll Pair Shortest Path Matrixn";
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
cout << iaFloyd[i][j] << "t";
}
cout << endl;
}
cout << "n";
return 0;
}C Code
/***************************************************************************
*File : 03AFloyd.c
*Description: Program to implement Floyd's Algorithm
*Author : Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
/******************************************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************************************/
int main(void)
{
int iN, i, j, k;
int iaFloyd[10][10], iaCost[10][10];
printf("n*********************************************************");
printf("n*tPROGRAM TO IMPLEMENT FLOYD'S ALGORITHMt*n");
printf("*********************************************************");
printf("nEnter the number of verticesn");
scanf("%d",&iN);
printf("nEnter the Cost adjacency Matrixn");
for(i=0;i<iN;i++)
for(j=0;j<iN;j++)
scanf("%d",&iaCost[i][j]);
printf("nInput Graphn");
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
printf("%dt",iaCost[i][j]);
}
printf("n");
}
printf("n");
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
iaFloyd[i][j] = iaCost[i][j];
}
}
for(k=0;k<iN;k++)
{
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
if(iaFloyd[i][j] > (iaFloyd[i][k] + iaFloyd[k][j]))
iaFloyd[i][j] = (iaFloyd[i][k] + iaFloyd[k][j]);
}
}
}
printf("nAll Pair Shortest Path Matrixn");
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
printf("%dt",iaFloyd[i][j]);
}
printf("n");
}
printf("n");
return 0;
}Input Graph
For this program lets consider the following graph
Output
*********************************************************
* PROGRAM TO IMPLEMENT FLOYD'S ALGORITHM *
*********************************************************
Enter the number of vertices
5
Enter the Cost adjacency Matrix
0 3 9999 7 9
3 0 4 2 9999
9999 4 0 5 6
7 2 5 0 4
9 9999 6 4 0
Input Graph
0 3 9999 7 9
3 0 4 2 9999
9999 4 0 5 6
7 2 5 0 4
9 9999 6 4 0
All Pair Shortest Path Matrix
0 3 7 5 9
3 0 4 2 6
7 4 0 5 6
5 2 5 0 4
9 6 6 4 0
Warshall’s Algorithm
Design and implement C/C++ Program to find the transitive closure using Warshal’s algorithm.
C++ Code
/******************************************************************************
*File : 03BWarshall.cpp
*Description: Program to find transitive closure of a given directed
* graph using Warshall's algorithm.
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <iostream>
using namespace std;
const int MAX = 100;
void WarshallTransitiveClosure(int graph[MAX][MAX], int numVert);
/******************************************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************************************/
int main(void)
{
int i, j, numVert;
int graph[MAX][MAX];
cout << "Warshall's Transitive Closure" << endl;
cout << "Enter the number of vertices : " ;
scanf("%d",&numVert);
cout << "Enter the adjacency matrix :-" << endl;
for (i=0; i<numVert; i++)
for (j=0; j<numVert; j++)
scanf("%d",&graph[i][j]);
WarshallTransitiveClosure(graph, numVert);
cout << "nThe transitive closure for the given graph is :-" << endl;
for (i=0; i<numVert; i++)
{
for (j=0; j<numVert; j++)
{
cout << graph[i][j] << "t";
}
cout << "" << endl;
}
return 0;
}
/******************************************************************************
*Function : WarshallTransitiveClosure
*Description : Function to transitive closure of a given directed
* graph using Warshall's algorithm.
*Input parameters:
* int graph[MAX][MAX] - adjacency matrix of the input graph
* int numVert - no of vertices in the graph
*RETURNS : no value
******************************************************************************/
void WarshallTransitiveClosure(int graph[MAX][MAX], int numVert)
{
int i,j,k;
for (k=0; k<numVert; k++)
{
for (i=0; i<numVert; i++)
{
for (j=0; j<numVert; j++)
{
if (graph[i][j] || (graph[i][k] && graph[k][j]))
graph[i][j] = 1;
}
}
}
}C Code
/******************************************************************************
*File : 03BWarshall.c
*Description: Program to find transitive closure of a given directed
* graph using Warshall's algorithm.
*Author : Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <stdio.h>
const int MAX = 100;
void WarshallTransitiveClosure(int graph[MAX][MAX], int numVert);
/******************************************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************************************/
int main(void)
{
int i, j, numVert;
int graph[MAX][MAX];
printf("Warshall's Transitive Closuren");
printf("Enter the number of vertices : ");
scanf("%d",&numVert);
printf("Enter the adjacency matrix :-n");
for (i=0; i<numVert; i++)
for (j=0; j<numVert; j++)
scanf("%d",&graph[i][j]);
WarshallTransitiveClosure(graph, numVert);
printf("nThe transitive closure for the given graph is :-n");
for (i=0; i<numVert; i++)
{
for (j=0; j<numVert; j++)
{
printf("%dt",graph[i][j]);
}
printf("n");
}
return 0;
}
/******************************************************************************
*Function : WarshallTransitiveClosure
*Description : Function to transitive closure of a given directed
* graph using Warshall's algorithm.
*Input parameters:
* int graph[MAX][MAX] - adjacency matrix of the input graph
* int numVert - no of vertices in the graph
*RETURNS : no value
******************************************************************************/
void WarshallTransitiveClosure(int graph[MAX][MAX], int numVert)
{
int i,j,k;
for (k=0; k<numVert; k++)
{
for (i=0; i<numVert; i++)
{
for (j=0; j<numVert; j++)
{
if (graph[i][j] || (graph[i][k] && graph[k][j]))
graph[i][j] = 1;
}
}
}
}Output
/***************************************
Warshall's Transitive Closure
***************************************/
Enter the number of vertices : 4
Enter the adjacency matrix :-
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
The transitive closure for the given graph is :-
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
/***************************************
Warshall's Transitive Closure
***************************************/
Enter the number of vertices : 4
Enter the adjacency matrix :-
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
The transitive closure for the given graph is :-
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Program 04
Dijkstra’s Algorithm
Design and implement C/C++ Program to find shortest paths from a given vertex in a weighted connected graph to other vertices using Dijkstra’s algorithm.
C++ Code
/******************************************************************************
*File : 04Dijkstra.cpp
*Description: Program to find shortest paths to other vertices using
* Dijkstra's algorithm.
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXNODES = 10,INF = 9999;
void fnDijkstra(int [][MAXNODES], int [], int [], int[], int, int, int);
/******************************************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************************************/
int main(void)
{
int n,cost[MAXNODES][MAXNODES],dist[MAXNODES],visited[MAXNODES],path[MAXNODES],i,j,source,dest;
cout << "nEnter the number of nodesn";
cin >> n;
cout << "Enter the Cost Matrixn" << endl;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
cin >> cost[i][j];
cout << "Enter the Source vertex" << endl;
cin >> source;
cout << "n//For Source Vertex : " << source << " shortest path to other vertices//"<< endl;
for (dest=0; dest < n; dest++)
{
fnDijkstra(cost,dist,path,visited,source,dest,n);
if (dist[dest] == INF)
cout << dest << " not reachable" << endl;
else
{
cout << endl;
i = dest;
do
{
cout << i << "<--";
i = path[i];
}while (i!= source);
cout << i << " = " << dist[dest] << endl;
}
}
return 0;
}
/******************************************************************************
*Function : fnDijkstra
*Description : Function to find shortest paths to other vertices
* using Dijkstra's algorithm.
*Input parameters:
* int c[][] - cost adjacency matrix of the graph
* int d[] - distance vector
* int p[] - path vector
* int s[] - vector to store visited information
* int so - source vertex
* int de - destination vertex
* int n - no of vertices in the graph
*RETURNS : no value
******************************************************************************/
void fnDijkstra(int c[MAXNODES][MAXNODES], int d[MAXNODES], int p[MAXNODES],
int s[MAXNODES], int so, int de, int n)
{
int i,j,a,b,min;
for (i=0;i<n;i++)
{
s[i] = 0;
d[i] = c[so][i];
p[i] = so;
}
s[so] = 1;
for (i=1;i<n;i++)
{
min = INF;
a = -1;
for (j=0;j<n;j++)
{
if (s[j] == 0)
{
if (d[j] < min)
{
min = d[j];
a = j;
}
}
}
if (a == -1) return;
s[a] = 1;
if (a == de) return;
for (b=0;b<n;b++)
{
if (s[b] == 0)
{
if (d[a] + c[a][b] < d[b])
{
d[b] = d[a] + c[a][b];
p[b] = a;
}
}
}
}
}C Code
/******************************************************************************
*File : 04Dijkstra.c
*Description: Program to find shortest paths to other vertices using
* Dijkstra's algorithm.
*Author : Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
const int MAXNODES = 10,INF = 9999;
void fnDijkstra(int [MAXNODES][MAXNODES], int [MAXNODES], int [MAXNODES], int[MAXNODES], int, int, int);
/******************************************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************************************/
int main(void)
{
int n,cost[MAXNODES][MAXNODES],dist[MAXNODES],visited[MAXNODES],path[MAXNODES],i,j,source,dest;
printf("\nEnter the number of nodes\n");
scanf("%d", &n);
printf("Enter the Cost Matrix\n\n");
for (i=0;i<n;i++)
for (j=0;j<n;j++)
scanf("%d", &cost[i][j]);
printf("Enter the Source vertex\n");
scanf("%d", &source);
printf("\n//For Source Vertex : %d shortest path to other vertices//\n", source);
for (dest=0; dest < n; dest++)
{
fnDijkstra(cost,dist,path,visited,source,dest,n);
if (dist[dest] == INF)
printf("%d not reachable\n\n", dest);
else
{
printf("\n");
i = dest;
do
{
printf("%d <--", i);
i = path[i];
}while (i!= source);
printf("%d = %d\n", i, dist[dest]);
}
}
return 0;
}
/******************************************************************************
*Function : fnDijkstra
*Description : Function to find shortest paths to other vertices
* using Dijkstra's algorithm.
*Input parameters:
* int c[][] - cost adjacency matrix of the graph
* int d[] - distance vector
* int p[] - path vector
* int s[] - vector to store visited information
* int so - source vertex
* int de - destination vertex
* int n - no of vertices in the graph
*RETURNS : no value
******************************************************************************/
void fnDijkstra(int c[MAXNODES][MAXNODES], int d[MAXNODES], int p[MAXNODES], int s[MAXNODES], int so, int de, int n)
{
int i,j,a,b,min;
for (i=0;i<n;i++)
{
s[i] = 0;
d[i] = c[so][i];
p[i] = so;
}
s[so] = 1;
for (i=1;i<n;i++)
{
min = INF;
a = -1;
for (j=0;j<n;j++)
{
if (s[j] == 0)
{
if (d[j] < min)
{
min = d[j];
a = j;
}
}
}
if (a == -1) return;
s[a] = 1;
if (a == de) return;
for (b=0;b<n;b++)
{
if (s[b] == 0)
{
if (d[a] + c[a][b] < d[b])
{
d[b] = d[a] + c[a][b];
p[b] = a;
}
}
}
}
}Input Graph
For this program lets consider the following graph
Output:
Enter the number of nodes
6
Enter the Cost Matrix
0 4 4 9999 9999 9999
4 0 2 9999 9999 9999
4 2 0 3 1 6
9999 9999 3 0 9999 2
9999 9999 1 9999 0 3
9999 9999 6 2 3 0
Enter the Source vertex
0
//For Source Vertex : 0 shortest path to other vertices//
0<--0 = 0
1<--0 = 4
2<--0 = 4
3<--2<--0 = 7
4<--2<--0 = 5
5<--4<--2<--0 = 8Program 05
Topological Ordering
Design and implement C/C++ Program to obtain the Topological ordering of vertices in a given digraph.
C++ Program
/******************************************************************************
*File : 05Topological.cpp
*Description : Program to find Topological ordering of nodes in a DAG
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int MAX = 10;
class Graph{
int iNum;
int iaGraph[MAX][MAX];
vector <int> jobVector;
public:
friend istream& operator>>(istream&, Graph&);
void fnCompTopoOrder();
void fnDispTopoOrder();
};
istream& operator>>(istream &in, Graph &g)
{
cout << "Enter the number of vertices : ";
in >> g.iNum;
cout << "nEnter the adjacency matrix (graph should be a DAG)" << endl;
for(int i=0;i<g.iNum;i++)
for(int j=0;j<g.iNum;j++)
in >> g.iaGraph[i][j];
return in;
}
void Graph::fnCompTopoOrder()
{
int i, j, k=0;
vector <int> inDegree(MAX);
stack <int> myStack;
for(i=0;i<iNum;i++)
{
inDegree[i] = 0;
for(j=0;j<iNum;j++)
{
inDegree[i] += iaGraph[j][i];
}
}
while(1)
{
for(i=0;i<iNum;i++)
{
if(inDegree[i] == 0)
{
myStack.push(i);
inDegree[i] = -1;
}
}
if(myStack.empty())
break;
jobVector.push_back(myStack.top());
myStack.pop();
for(i=0;i<iNum;i++)
{
if(iaGraph[jobVector[k]][i])
{
inDegree[i]--;
}
}
k++;
}
}
void Graph::fnDispTopoOrder()
{
cout << "Topological Ordering (JOB SEQUENCE) is:";
for(size_t i=0; i<jobVector.size(); i++)
{
cout << jobVector[i]+1 << "t";
}
cout << endl;
}
int main()
{
Graph myGraph;
cin >> myGraph;
myGraph.fnCompTopoOrder();
myGraph.fnDispTopoOrder();
return 0;
}
C Program
/******************************************************************************
*File : 05Topological.c
*Description : Program to find Topological ordering of nodes in a DAG
*Author : Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <stdio.h>
const int MAX = 10;
void fnTopological(int a[MAX][MAX], int n);
/******************************************************************************
*Function : main
*Function parameters:
* int argc - no of commamd line arguments
* char **argv - vector to store command line argumennts
*RETURNS : 0 on success
******************************************************************************/
int main( int argc, char **argv)
{
int graph[MAX][MAX],n;
int i,j;
printf("Topological Sorting Algorithm -n");
printf("nEnter the number of vertices : ");
scanf("%d",&n);
printf("Enter the adjacency matrix (graph should be a DAG)n");
for (i=0; i<n; i++)
for (j=0; j<n; j++)
scanf("%d",&graph[i][j]);
fnTopological(graph,n);
printf("n");
return 0;
}
/******************************************************************************
*Function: fnTopological
*Description: Function to find Topological ordering of nodes in a DAG
*Input parameters:
* int graph[MAX][MAX] - adjacency matrix of the input graph
* int n - no of vertices in the graph
*RETURNS: no value
******************************************************************************/
void fnTopological(int graph[MAX][MAX], int n)
{
int in[MAX], out[MAX], stack[MAX], top=-1;
int i,j,k=0;
for (i=0;i<n;i++)
{
in[i] = 0;
for (j=0; j<n; j++)
if (graph[j][i] == 1)
in[i]++;
}
while(1)
{
for (i=0;i<n;i++)
{
if (in[i] == 0)
{
stack[++top] = i;
in[i] = -1;
}
}
if (top == -1)
break;
out[k] = stack[top--];
for(i=0;i<n;i++)
{
if (graph[out[k]][i] == 1)
in[i]--;
}
k++;
}
printf("Topological Sorting (JOB SEQUENCE) is:- n");
for (i=0;i<k;i++)
printf("%dt", out[i] + 1);
printf("n");
}
Input Graph
Output
Enter the number of vertices : 5
Enter the adjacency matrix -
0 0 1 0 0
0 0 1 0 0
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0
Topological Sorting (JOB SEQUENCE) is:-
2 1 3 4 5
Program 06
0/1 Knapsack problem
Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic Programming method.
C++ Code
/********************************************************************************
*File : 06Knapsack.cpp
*Description: Program to find solution to 0/1 Knapsack problem using Dynamic Programming
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
********************************************************************************/
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
const int MAX = 10;
inline int max(int x, int y)
{
return (x>y)?x:y;
}
class Knapsack
{
int totalProfit;
int weight[MAX];
int profit[MAX];
int capacity;
int numOfObj;
int subset[MAX];
int table[MAX][MAX];
public:
Knapsack();
void fnReadKnapDetails();
void fnCalcProfit();
void fnFindSubSet();
};
void Knapsack::fnReadKnapDetails()
{
int i;
cout << "Enter the maxium number of objects : ";
cin >> numOfObj;
cout << "Enter the weights : n";
for (i=1; i<=numOfObj; i++)
{
cout << "Weight " << i << ": ";
cin >> weight[i];
}
cout << "nEnter the profits : n";
for (i=1; i<=numOfObj; i++)
{
cout << "Profit " << i << ": ";
cin >> profit[i];
}
cout << "nEnter the maximum capacity : ";
cin >> capacity;
}
Knapsack :: Knapsack()
{
int i;
totalProfit = 0;
for( i=1; i<=numOfObj; i++)
subset[i] = 0;
}
void Knapsack::fnCalcProfit()
{
int i,j;
for (j=0; j<=capacity; j++)
table[0][j] = 0;
for (i=0; i<=numOfObj; i++)
table[i][0] = 0;
for (i=1; i<=numOfObj; i++)
{
for (j=1; j<=capacity; j++)
{
if (j-weight[i] < 0)
table[i][j] = table[i-1][j];
else
table[i][j] = max(table[i-1][j], profit[i] + table[i-1][j-weight[i]]);
}
}
totalProfit = table[numOfObj][capacity];
cout << "nProfit Matrix" << endl;
for(i=0;i<=numOfObj; i++)
{
for (j=0; j<=capacity; j++)
{
cout << setw(6) << table[i][j];
}
cout << endl;
}
cout << endl;
}
void Knapsack::fnFindSubSet()
{
int i,j;
i = numOfObj;
j = capacity;
while (i >= 1 && j >= 1)
{
if (table[i][j] != table[i-1][j])
{
subset[i] = 1;
j = j - weight[i];
}
i--;
}
cout << "Items selected for the Knapsack are : " ;
for(i=1;i<=numOfObj;i++)
{
if(subset[i] == 1)
cout << i << " ";
}
cout << endl;
cout << "Total Profit earned is " << totalProfit << endl;
}
int main()
{
Knapsack knapsackObj;
knapsackObj.fnReadKnapDetails();
knapsackObj.fnCalcProfit();
knapsackObj.fnFindSubSet();
return 0;
}
Input Sample
Lets consider this sample input for the 0/1 Knapsack Problem.
Knapsack Capacity : 5
| Item | Weight | Profit |
| 1 | 2 | 12 |
| 2 | 1 | 10 |
| 3 | 3 | 20 |
| 4 | 2 | 15 |
Output
Enter the maxium number of objects : 4
Enter the weights :
Weight 1: 2
Weight 2: 1
Weight 3: 3
Weight 4: 2
Enter the profits :
Profit 1: 12
Profit 2: 10
Profit 3: 20
Profit 4: 15
Enter the maximum capacity : 5
Profit Matrix
0 0 0 0 0 0
0 0 12 12 12 12
0 10 12 22 22 22
0 10 12 22 30 32
0 10 15 25 30 37
Items selected for the Knapsack are : 1 2 4
Total Profit earned is 37
Program 07
Knapsack problem using Greedy method.
Design and implement C/C++ Program to solve discrete Knapsack and continuous Knapsack problems using greedy approximation method.
C++ Code
/********************************************************************************
*File : 07GreedyKnapsack.cpp
*Description: Program to find solution to discrete & continous Knapsack problem using Greedy Method
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
********************************************************************************/
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <cstdlib>
using namespace std;
typedef struct{
int profit;
int weight;
float profitRatio;
float fraction;
}Item;
int main()
{
vector <Item> itemList;
int iNum, i, iPos;
float knCap, remCap, totProfit;
Item a;
cout << "Enter the number of items : " ;
cin >> iNum;
cout << "Enter Knapsack capacity : ";
cin >> knCap;
//for each item calculate the profit ratio and add that item to the item list in sorted order of profits
for(i=0;i<iNum;i++)
{
cout << "Enter profit : "; cin >> a.profit;
cout << "Enter weight : "; cin >> a.weight;
a.profitRatio = (float)a.profit / a.weight;
a.fraction = 0.0f;
//cout << a.profitRatio << endl;
if (itemList.size() == 0)
{
itemList.push_back(a);
}
else
{
iPos=0;
while(a.profitRatio < itemList[iPos].profitRatio) iPos++;
itemList.insert(itemList.begin() + iPos,a);
}
}
remCap = knCap;
totProfit = 0.0;
for(i=0;i<iNum;i++)
{
a = itemList[i];
if(a.weight < remCap)
{
itemList[i].fraction = 1.0;
remCap -= itemList[i].weight;
totProfit += itemList[i].profit;
}
if(remCap == 0)
break;
}
cout << "nDISCRETE KNAPSACK GREEDY SOLUTIONn";
cout << "ItemtWeighttProfittFraction_Chosenn";
for(i=0;i<iNum;i++)
{
cout <<setw(4) << i+1 << "t" << setw(6) << itemList[i].weight << "t" << setw(6) << itemList[i].profit << "t" << setw(6) << setprecision(2) << itemList[i].fraction << endl;
}
cout << "nTotal Profit Earned : " << fixed << totProfit << endl;
remCap = knCap;
totProfit = 0.0;
for(i=0;i<iNum;i++)
{
itemList[i].fraction = 0.0f;
}
for(i=0;i<iNum;i++)
{
a = itemList[i];
if(a.weight < remCap)
{
itemList[i].fraction = 1.0;
remCap -= itemList[i].weight;
totProfit += itemList[i].profit;
}
else
{
itemList[i].fraction = remCap / itemList[i].weight;
remCap -= itemList[i].weight * itemList[i].fraction;
totProfit += itemList[i].profit * itemList[i].fraction;
}
if(remCap == 0)
break;
}
cout << "nCONTINUOUS KNAPSACK GREEDY SOLUTIONn";
cout << "ItemtWeighttProfittFraction Chosenn";
for(i=0;i<iNum;i++)
{
cout << i+1 << "t" << itemList[i].weight << "t" << itemList[i].profit << "t" << setprecision(2) << itemList[i].fraction << endl;
}
cout << "nTotal Profit Earned : " << fixed << totProfit << endl;
return 0;
}
Input sample
Lets consider this sample input for the 0/1 Knapsack Problem.
Knapsack Capacity : 5
| Item | Weight | Profit |
| 1 | 5 | 30 |
| 2 | 10 | 40 |
| 3 | 15 | 45 |
| 4 | 22 | 77 |
| 5 | 25 | 90 |
Output
Enter the number of items : 4
Enter Knapsack capacity : 5
Enter profit : 12
Enter weight : 2
Enter profit : 10
Enter weight : 1
Enter profit : 20
Enter weight : 3
Enter profit : 15
Enter weight : 2
DISCRETE KNAPSACK GREEDY SOLUTION
Item Weight Profit Fraction_Chosen
1 1 10 1
2 2 15 1
3 3 20 0
4 2 12 0
Total Profit Earned : 25.00
CONTINUOUS KNAPSACK GREEDY SOLUTION
Item Weight Profit Fraction Chosen
1 1 10 1.00
2 2 15 1.00
3 3 20 0.67
4 2 12 0.00
Total Profit Earned : 38.33
Program 08
Subset Sum Problem
Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,…..,sn} of n positive
integers whose sum is equal to a given positive integer d.
C++ Code
/******************************************************
*File : 08SubSetSum.cpp
*Description: Program to solve Subset sum problem.
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************/
#include <iostream>
using namespace std;
// Constant definitions
const int MAX = 100;
// class definitions
class SubSet
{
int stk[MAX], set[MAX];
int size, top, count;
public:
SubSet()
{
top = -1;
count = 0;
}
void getInfo(void);
void push(int data);
void pop(void);
void display(void);
int fnFindSubset(int pos, int sum);
};
/******************************************************
*Function : getInfo
*Description: Function to read input
*Input parameters: no parameters
*RETURNS : no value
******************************************************/
void SubSet :: getInfo(void)
{
int i;
cout << "Enter the maximum number of elements : ";
cin >> size;
cout << "Enter the values of the elements : n";
for (i=1; i<=size; i++)
cin >> set[i];
}
/******************************************************
*Function : push
*Description: Function to push an element on to the stack
*Input parameters:
*int data - value to be pushed on to the stack
*RETURNS : no value
******************************************************/
void SubSet :: push(int data)
{
stk[++top] = data;
}
/******************************************************
*Function : pop
*Description: Function to pop an element from the stack
*Input parameters: no parameters
*RETURNS : no value
******************************************************/
void SubSet :: pop(void)
{
top--;
}
/******************************************************
*Function : display
*Description: Function to display solution to sub set sum problem
*Input parameters: no parameters
*RETURNS : no value
******************************************************/
void SubSet :: display()
{
int i;
cout << "nSOLUTION #"<< ++count <<" ISn{ ";
for (i=0; i<=top; i++)
cout << stk[i] << " ";
cout << "}" << endl;
}
/******************************************************
*Function : fnFindSubset
*Description : Function to solve Subset sum problem.
*Input parameters:
* int pos - position
* int sum - sum of elements
*RETURNS : returns 1 if solution exists or zero otherwise
******************************************************/
int SubSet :: fnFindSubset(int pos, int sum)
{
int i;
static int foundSoln = 0;
if (sum>0)
{
for (i=pos; i<=size; i++)
{
push(set[i]);
fnFindSubset(i+1, sum - set[i]);
pop();
}
}
if (sum == 0)
{
display();
foundSoln = 1;
}
return foundSoln;
}
/******************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************/
int main(void)
{
int sum;
SubSet set1;
set1.getInfo();
cout << "Enter the sum value : ";
cin >> sum;
cout << endl;
if (!set1.fnFindSubset(1, sum))
cout << "nThe problem instance doesnt have any solution." << endl;
else
cout << "nThe above-mentioned sets are the required solution to " <<
"the given instance." << endl;
return 0;
}C Code
/******************************************************
*File : 08SubSetSum.c
*Description: Program to solve Subset sum problem.
*Author : Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************/#include<stdio.h>
int subset(int n,int d,int values[]);
int main()
{
int n,d,i,values[10];
printf("Enter the number of elements : ");
scanf("%d",&n);
printf("Enter the values of the elements (in ascending order) : n");
for(i=1;i<=n;i++)
scanf("%d",&values[i]);
printf("Enter the sum value : ");
scanf("%d",&d);
printf("n");
if (!subset(n,d,values))
printf("nThe problem instance doesnt have any solution.n");
else
printf("nThe above-mentioned sets are the required solution to the given instance.n");
return 0;
}
int subset(int n,int d,int values[])
{
int sum,k,i,included[10];
static int foundSoln = 0;
static int count = 0;
for(i=1;i<=n;i++)
included[i] = 0;
sum = 0;
k = 1;
included[k] = 1;
while(1)
{
if(k <= n && included[k] == 1)
{
if(sum + values[k] == d)
{
foundSoln = 1;
++count;
printf("SOLUTION #%d IS n{ ", count);
for(i=1;i<=n;i++)
{
if(included[i] == 1)
printf("%d ",values[i]);
}
printf(" }nn");
included[k] = 0;
}
else if(sum + values[k] < d)
sum += values[k];
else
included[k] = 0;
}
else
{
k--;
while(k>0 && included[k] == 0)
{
k--;
}
if(k == 0)
break;
included[k] = 0;
sum = sum - values[k];
}
k = k+1;
included[k] = 1;
}
return foundSoln;
}
Output
Enter the number of elements : 5
Enter the values of the elements (in ascending order) :
1 2 5 6 8
Enter the sum value : 9
SOLUTION #1 IS
{ 1 2 6 }
SOLUTION #2 IS
{ 1 8 }
The above-mentioned sets are the required solution to the given instance.
#########################################################################
Enter the number of elements : 3
Enter the values of the elements (in ascending order) :
1 3 5
Enter the sum value : 7
The problem instance doesnt have any solution.Program 09
Selection Sort
Design and implement C/C++ Program to sort a given set of n integer elements using Selection Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.
C++ Code
/******************************************************************************
*File : 09SelectionSort.cpp
*Description : Program to sort an array using Selection Sort
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
class SelectionSort{
vector <int> numList;
int iNum;
public:
void fnGenRandArray(int);
void fnSelectionSort();
void fnDispArray();
void fnSwap(int&, int&);
};
int main( int argc, char **argv)
{
struct timespec tv;
int iChoice, i, iNum;
double dStart, dEnd;
SelectionSort myListObj;
ofstream fout("SelectionPlot.dat", ios::out);
for(;;)
{
cout << "n1.Selection Sortn2.Plot the Graphn3.Exit" ;
cout << "nEnter your choicen";
cin >> iChoice;
switch(iChoice)
{
case 1:
cout << "nEnter number of elements to sort : "; cin >> iNum;
myListObj.fnGenRandArray(iNum);
cout << "nUnsorted Array" << endl;
myListObj.fnDispArray();
myListObj.fnSelectionSort();
cout << "nSorted Array" << endl;
myListObj.fnDispArray();
break;
case 2: for(i=100;i<20000;i+=100)
{
myListObj.fnGenRandArray(i);
clock_gettime(CLOCK_REALTIME, &tv);
dStart = tv.tv_sec + tv.tv_nsec/1000000000.0;
myListObj.fnSelectionSort();
clock_gettime(CLOCK_REALTIME, &tv);
dEnd = tv.tv_sec + tv.tv_nsec/1000000000.0;
fout << i << "t" << setprecision(10) << dEnd - dStart << endl;
}
cout << "nData File generated and stored in file < SelectionPlot.dat >.n Use a plotting utilityn";
break;
case 3:
exit(0);
}
}
fout.close();
return 0;
}
/******************************************************************************
*Function: fnSelectionSort
*Description: Function to sort elements in an iaArray using Quick Sort
*Function parameters:
* int n - number of elements to be sorted
******************************************************************************/
void SelectionSort :: fnSelectionSort()
{
int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < iNum-1; i++) {
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < iNum; j++) {
if (numList[j] < numList[min_idx])
min_idx = j;
}
// Swap the found minimum element with the first element
fnSwap(numList[min_idx], numList[i]);
}
}
void SelectionSort::fnGenRandArray(int n)
{
int i, iVal;
numList.clear();
srand(time(NULL));
for(i=0;i<n;i++)
{
iVal = rand()%10000;
numList.push_back(iVal);
}
iNum = n;
}
void SelectionSort::fnDispArray()
{
int i;
for(i=0;i<iNum;i++)
{
cout << setw(8) << numList[i] << endl;
}
}
void SelectionSort::fnSwap(int &a,int &b)
{
int t;
t = a;
a = b;
b = t;
}C Code
/********************************************************************************
*File : 09SelectionSort.c
*Description : Program to sort an array using Selection Sort
*Author : Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
void fnGenRandInput(int [], int);
void fnDispArray( int [], int);
void fnSelectionSort(int [], int);
/******************************************************************************
*Function : main
*Function parameters:
* int argc - no of commamd line arguments
* char **argv - vector to store command line argumennts
*RETURNS : 0 on success
******************************************************************************/
int main( int argc, char **argv)
{
FILE *fp;
struct timeval tv;
double dStart,dEnd;
int iaArr[500000],iNum,i,iChoice;
for(;;)
{
printf("n1.Plot the Graphn2.Selection Sortn3.Exit");
printf("nEnter your choicen");
scanf("%d",&iChoice);
switch(iChoice)
{
case 1:
fp = fopen("SelectionPlot.dat","w");
for(i=100;i<20000;i+=100)
{
fnGenRandInput(iaArr,i);
gettimeofday(&tv,NULL);
dStart = tv.tv_sec + (tv.tv_usec/1000000.0);
fnSelectionSort(iaArr,i);
gettimeofday(&tv,NULL);
dEnd = tv.tv_sec + (tv.tv_usec/1000000.0);
fprintf(fp,"%dt%lfn",i,dEnd-dStart);
}
fclose(fp);
printf("nData File generated and stored in file < SelectionPlot.dat >.n Use a plotting utilityn");
break;
case 2:
printf("nEnter the number of elements to sortn");
scanf("%d",&iNum);
printf("nUnsorted Arrayn");
fnGenRandInput(iaArr,iNum);
fnDispArray(iaArr,iNum);
fnSelectionSort(iaArr,iNum);
printf("nSorted Arrayn");
fnDispArray(iaArr,iNum);
break;
case 3:
exit(0);
}
}
return 0;
}
/******************************************************************************
*Function : GenRandInput
*Description : Function to generate a fixed number of random elements
*Function parameters:
* int X[] - array to hold integers
* int n - no of elements in the array
*RETURNS :no return value
******************************************************************************/
void fnGenRandInput(int X[], int n)
{
int i;
srand(time(NULL));
for(i=0;i<n;i++)
{
X[i] = rand()%10000;
}
}
/******************************************************************************
*Function : DispArray
*Description : Function to display elements of an array
*Function parameters:
* int X[] - array to hold integers
* int n - no of elements in the array
*RETURNS : no return value
******************************************************************************/
void fnDispArray( int X[], int n)
{
int i;
for(i=0;i<n;i++)
printf(" %5d n",X[i]);
}
/******************************************************************************
*Function : fnSelectionSort
*Description : Function to sort elements in an array using Selection Sort
*Input parameters:
* int X[] - array to hold integers
* int n - no of elements in the array
*RETURNS : no return value
******************************************************************************/
void fnSelectionSort(int X[], int n)
{
int i,j,iTemp,iMin;
for(i=0;i<n;i++)
{
iMin = i;
for(j = i+1;j<n;j++)
{
if(X[j] < X[iMin])
iMin = j;
}
iTemp = X[i];
X[i] = X[iMin];
X[iMin] = iTemp;
}
}
Plotting using Gnuplot Utility
Gnuplot is one of the popular tools used for plotting. You can install using the following command on Ubuntu.
$ sudo apt install gnuplotAfter executing option 2 in the program output we see that a file SelectPlot.dat was created in your local folder which contains running times for various input sizes. The first column specifies the input size and the second specifies the running time in microseconds.
Contents of SelectPlot.dat
$ head SelectionPlot.dat
100 2.956390381e-05
200 0.0001039505005
300 0.0002217292786
400 0.0004942417145
500 0.0006952285767
600 0.000981092453
700 0.001403331757
800 0.001530170441
900 0.001908540726
1000 0.002341508865
Plotting Script for Gnuplot
We will now see how to generate a plot graph of data contained in SelectPlot.dat and store it as an image. For that let’s write a gnuplot script file called 01SelectPlot.gpl. The contents of which are shown below
# Gnuplot script file for plotting data in file "SelectionPlot.dat"
# This file is called 09SelectPlot.gpl
set terminal png font arial
set title "Time Complexity for Selection Sort"
set autoscale
set xlabel "Size of Input"
set ylabel "Sorting Time (microseconds)"
set grid
set output "SelectionPlot.png"
plot "SelectionPlot.dat" t 'Selection Sort' with linesThe above file illustrates how to set various properties in the plot using the set command. Observe that the last line in the script generates the graph using plot command.
To execute the Gnuplot script you have to give the following command:
$ gnuplot 01SelectPlot.gplYou can now see that an image file by name SelectPlot.png containing the graph will be created in your local folder.
Output
1.Selection Sort
2.Plot the Graph
3.Exit
Enter your choice
1
Enter number of elements to sort : 5
Unsorted Array
6976
1561
4417
544
3179
Sorted Array
544
1561
3179
4417
6976
1.Selection Sort
2.Plot the Graph
3.Exit
Enter your choice
2
Data File generated and stored in file < SelectionPlot.dat >.
Use a plotting utility
1.Selection Sort
2.Plot the Graph
3.Exit
Enter your choice
3
Time Complexity Analysis
Worst Case – O(n2)
Average Case – O(n2)
Best Case – O(n2)
Program 10
Quick Sort
Design and implement C/C++ Program to sort a given set of n integer elements using Quick Sort method and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.
C++ Code
/******************************************************************************
*File : 10QuickSort.cpp
*Description : Program to sort an array using Quick Sort
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
class QuickSort{
vector <int> numList;
int iNum;
public:
void fnGenRandArray(int);
void fnQuickSort(int, int);
void fnDispArray();
int fnPartition(int ,int);
void fnSwap(int&, int&);
};
int main( int argc, char **argv)
{
struct timespec tv;
int iChoice, i, iNum;
double dStart, dEnd;
QuickSort myListObj;
ofstream fout("QuickPlot.dat", ios::out);
for(;;)
{
cout << "n1.Quick Sortn2.Plot the Graphn3.Exit" ;
cout << "nEnter your choicen";
cin >> iChoice;
switch(iChoice)
{
case 1:
cout << "nEnter number of elements to sort : "; cin >> iNum;
myListObj.fnGenRandArray(iNum);
cout << "nUnsorted Array" << endl;
myListObj.fnDispArray();
myListObj.fnQuickSort(0,iNum-1);
cout << "nSorted Array" << endl;
myListObj.fnDispArray();
break;
case 2: for(i=100;i<100000;i+=100)
{
myListObj.fnGenRandArray(i);
clock_gettime(CLOCK_REALTIME, &tv);
dStart = tv.tv_sec + tv.tv_nsec/1000000000.0;
myListObj.fnQuickSort(0,i-1);
clock_gettime(CLOCK_REALTIME, &tv);
dEnd = tv.tv_sec + tv.tv_nsec/1000000000.0;
fout << i << "t" << setprecision(10) << dEnd - dStart << endl;
}
cout << "nData File generated and stored in file < QuickPlot.dat >.n Use a plotting utilityn";
break;
case 3:
exit(0);
}
}
fout.close();
return 0;
}
/******************************************************************************
*Function: fnPartition
*Description: Function to partition an iaArray using First element as Pivot
*Function parameters:
* int l - start index of the subiaArray to be sorted
* int r - end index of the subiaArray to be sorted
*RETURNS: integer value specifying the location of partition
******************************************************************************/
int QuickSort :: fnPartition(int l, int r)
{
int i,j;
int p;
p = numList[l];
i = l;
j = r+1;
do
{
do { i++; } while (numList[i] < p);
do { j--; } while (numList[j] > p);
fnSwap(numList[i], numList[j]);
}while (i<j);
fnSwap(numList[i], numList[j]);
fnSwap(numList[l], numList[j]);
return j;
}
/******************************************************************************
*Function: fnQuickSort
*Description: Function to sort elements in an iaArray using Quick Sort
*Function parameters:
* int l - start index of the subiaArray to be sorted
* int r - end index of the subiaArray to be sorted*RETURNS : no value
******************************************************************************/
void QuickSort :: fnQuickSort(int l, int r)
{
int s;
if (l < r)
{
s = fnPartition(l, r);
fnQuickSort(l, s-1);
fnQuickSort(s+1, r);
}
}
void QuickSort::fnGenRandArray(int n)
{
int i, iVal;
numList.clear();
srand(time(NULL));
for(i=0;i<n;i++)
{
iVal = rand()%10000;
numList.push_back(iVal);
}
iNum = n;
}
void QuickSort::fnDispArray()
{
int i;
for(i=0;i<iNum;i++)
{
cout << setw(8) << numList[i] << endl;
}
}
void QuickSort::fnSwap(int &a,int &b)
{
int t;
t = a;
a = b;
b = t;
}C Code
/******************************************************************************
*File : 10QuickSort.c
*Description : Program to sort an array using Quick Sort
*Author : Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
void fnGenRandInput(int [], int);
void fnDispArray( int [], int);
int fnPartition(int [], int , int);
void fnQuickSort(int [], int , int);
void fnSwap(int*, int*);
void fnSwap(int *a, int *b)
{
int t = *a; *a = *b; *b = t;
}
/******************************************************************************
*Function : main
*Function parameters:
* int argc - no of commamd line arguments
* char **argv - vector to store command line argumennts
*RETURNS : 0 on success
******************************************************************************/
int main( int argc, char **argv)
{
FILE *fp;
struct timeval tv;
double dStart,dEnd;
int iaArr[500000],iNum,i,iChoice;
for(;;)
{
printf("\n1.Plot the Graph\n2.QuickSort\n3.Exit");
printf("\nEnter your choice\n");
scanf("%d",&iChoice);
switch(iChoice)
{
case 1:
fp = fopen("QuickPlot.dat","w");
for(i=100;i<100000;i+=100)
{
fnGenRandInput(iaArr,i);
gettimeofday(&tv,NULL);
dStart = tv.tv_sec + (tv.tv_usec/1000000.0);
fnQuickSort(iaArr,0,i-1);
gettimeofday(&tv,NULL);
dEnd = tv.tv_sec + (tv.tv_usec/1000000.0);
fprintf(fp,"%d\t%lf\n",i,dEnd-dStart);
}
fclose(fp);
printf("\nData File generated and stored in file < QuickPlot.dat >.\n Use a plotting utility\n");
break;
case 2:
printf("\nEnter the number of elements to sort\n");
scanf("%d",&iNum);
printf("\nUnsorted Array\n");
fnGenRandInput(iaArr,iNum);
fnDispArray(iaArr,iNum);
fnQuickSort(iaArr,0,iNum-1);
printf("\nSorted Array\n");
fnDispArray(iaArr,iNum);
break;
case 3:
exit(0);
}
}
return 0;
}
/******************************************************************************
*Function: fnPartition
*Description: Function to partition an iaArray using First element as Pivot
*Function parameters:
* int a[] - iaArray to hold integers
* int l - start index of the subiaArray to be sorted
* int r - end index of the subiaArray to be sorted
*RETURNS: integer value specifying the location of partition
******************************************************************************/
int fnPartition(int a[], int l, int r)
{
int i,j;
int p;
p = a[l];
i = l;
j = r+1;
do
{
do { i++; } while (a[i] < p);
do { j--; } while (a[j] > p);
fnSwap(&a[i], &a[j]);
}while (i<j);
fnSwap(&a[i], &a[j]);
fnSwap(&a[l], &a[j]);
return j;
}
/******************************************************************************
*Function: fnQuickSort
*Description: Function to sort elements in an iaArray using Quick Sort
*Function parameters:
* int a[] - iaArray to hold integers
* int l - start index of the subiaArray to be sorted
* int r - end index of the subiaArray to be sorted*RETURNS : no value
******************************************************************************/
void fnQuickSort(int a[], int l, int r)
{
int s;
if (l < r)
{
s = fnPartition(a, l, r);
fnQuickSort(a, l, s-1);
fnQuickSort(a, s+1, r);
}
}
/******************************************************************************
*Function : GenRandInput
*Description : Function to generate a fixed number of random elements
*Function parameters:
* int X[] - array to hold integers
* int n - no of elements in the array
*RETURNS :no return value
******************************************************************************/
void fnGenRandInput(int X[], int n)
{
srand(time(NULL));
for(int i=0;i<n;i++)
{
X[i] = rand()%10000;
}
}
/******************************************************************************
*Function : DispArray
*Description : Function to display elements of an array
*Function parameters:
* int X[] - array to hold integers
* int n - no of elements in the array
*RETURNS : no return value
******************************************************************************/
void fnDispArray( int X[], int n)
{
for(int i=0;i<n;i++)
printf(" %5d \n",X[i]);
}Output
1.MergeSort
2.Plot the Graph
3.Exit
Enter your choice
1
Enter number of elements to sort : 6
Unsorted Array
4680
2144
465
5406
8471
3602
Sorted Array
465
2144
3602
4680
5406
8471
1.MergeSort
2.Plot the Graph
3.Exit
Enter your choice
2
Data File generated and stored in file < MergePlot.dat >.
Use a plotting utility
1.MergeSort
2.Plot the Graph
3.Exit
Enter your choice
3
Plotting Script for Gnuplot
We will now see how to generate a plot graph of data contained in QuickPlot.dat and store it as an image. Let’s write a gnuplot script file called 03QuickPlot.gpl to do the same. The contents of which are shown below
To execute the Gnuplot script you have to give the following command:
# Gnuplot script file for plotting data in file "QuickPlot.dat"
# This file is called 10QuickPlot.gpl
set terminal png font arial
set title "Time Complexity for Quick Sort"
set autoscale
set xlabel "Size of Input"
set ylabel "Sorting Time (microseconds)"
set grid
set output "QuickPlot.png"
plot "QuickPlot.dat" t 'Quick Sort' with lines$ gnuplot 03QuickPlot.gplYou can now see that an image file by name QuickPlot.png containing the graph will be created in your local folder.
Time Complexity Analysis of Quick Sort
Worst Case – O(n2)
Average Case – O(n*log n)
Best Case – O(n*log n)
Program 11
Merge Sort
Design and implement C/C++ Program to sort a given set of n integer elements using Merge Sort method and compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.
C++ Code
/******************************************************************************
*File : 11MergeSort.cpp
*Description : Program to sort an array using Merge Sort
*Author: Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
class MergeSort{
vector <int> numList;
int iNum;
public:
void fnGenRandArray(int);
void fnSortArray(int, int);
void fnDispArray();
void fnMerge(int ,int ,int);
};
int main( int argc, char **argv)
{
struct timespec tv;
int iChoice, i, iNum;
double dStart, dEnd;
MergeSort myListObj;
ofstream fout("MergePlot.dat", ios::out);
for(;;)
{
cout << "n1.MergeSortn2.Plot the Graphn3.Exit" ;
cout << "nEnter your choicen";
cin >> iChoice;
switch(iChoice)
{
case 1:
cout << "nEnter number of elements to sort : "; cin >> iNum;
myListObj.fnGenRandArray(iNum);
cout << "nUnsorted Array" << endl;
myListObj.fnDispArray();
myListObj.fnSortArray(0,iNum-1);
cout << "nSorted Array" << endl;
myListObj.fnDispArray();
break;
case 2: for(i=100;i<100000;i+=100)
{
myListObj.fnGenRandArray(i);
clock_gettime(CLOCK_REALTIME, &tv);
dStart = tv.tv_sec + tv.tv_nsec/1000000000.0;
myListObj.fnSortArray(0,i-1);
clock_gettime(CLOCK_REALTIME, &tv);
dEnd = tv.tv_sec + tv.tv_nsec/1000000000.0;
fout << i << "t" << setprecision(10) << dEnd - dStart << endl;
}
cout << "nData File generated and stored in file < MergePlot.dat >.n Use a plotting utilityn";
break;
case 3:
exit(0);
}
}
fout.close();
return 0;
}
void MergeSort::fnGenRandArray(int n)
{
int i, iVal;
numList.clear();
srand(time(NULL));
for(i=0;i<n;i++)
{
iVal = rand()%10000;
numList.push_back(iVal);
}
iNum = n;
}
void MergeSort::fnDispArray()
{
int i;
for(i=0;i<iNum;i++)
{
cout << setw(8) << numList[i] << endl;
}
}
void MergeSort::fnSortArray(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
fnSortArray(low,mid);
fnSortArray(mid+1,high);
fnMerge(low,mid,high);
}
}
void MergeSort::fnMerge(int low,int mid,int high)
{
vector <int> b(0);
int i,j;
i=low;
j=mid+1;
int k=0;
while(i<=mid && j<=high)
{
if(numList[i]<numList[j])
b.push_back(numList[i++]);
else
b.push_back(numList[j++]);
}
while(i<=mid)
b.push_back(numList[i++]);
while(j<=high)
b.push_back(numList[j++]);
for (i=low;i<=high;i++)
{
numList[low+k] = b[k];
k++;
}
}
C Code
/******************************************************************************
*File : 11MergeSort.c
*Description : Program to sort an array using Merge Sort
*Author: Prabodh C P
*Compiler : gcc compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
void fnGenRandInput(int [], int);
void fnDispArray( int [], int);
void fnMerge(int [], int ,int ,int);
void fnMergeSort(int [], int , int);
/******************************************************************************
*Function : main
*Function parameters:
* int argc - no of commamd line arguments
* char **argv - vector to store command line argumennts
*RETURNS : 0 on success
******************************************************************************/
int main( int argc, char **argv)
{
FILE *fp;
struct timeval tv;
double dStart,dEnd;
int iaArr[500000],iNum,i,iChoice;
for(;;)
{
printf("\n1.Plot the Graph\n2.MergeSort\n3.Exit");
printf("\nEnter your choice\n");
scanf("%d",&iChoice);
switch(iChoice)
{
case 1:
fp = fopen("MergePlot.dat","w");
for(i=100;i<100000;i+=100)
{
fnGenRandInput(iaArr,i);
gettimeofday(&tv,NULL);
dStart = tv.tv_sec + (tv.tv_usec/1000000.0);
fnMergeSort(iaArr,0,i-1);
gettimeofday(&tv,NULL);
dEnd = tv.tv_sec + (tv.tv_usec/1000000.0);
fprintf(fp,"%d\t%lf\n",i,dEnd-dStart);
}
fclose(fp);
printf("\nData File generated and stored in file < MergePlot.dat >.\n Use a plotting utility\n");
break;
case 2:
printf("\nEnter the number of elements to sort\n");
scanf("%d",&iNum);
printf("\nUnsorted Array\n");
fnGenRandInput(iaArr,iNum);
fnDispArray(iaArr,iNum);
fnMergeSort(iaArr,0,iNum-1);
printf("\nSorted Array\n");
fnDispArray(iaArr,iNum);
break;
case 3:
exit(0);
}
}
return 0;
}
/******************************************************************************
*Function : fnMerge
*Description : Function to merge two sorted arrays
*Function parameters:
* int a[] - iaArray to hold integers
* int low - start index of the subiaArray to be sorted
* int mid - mid index of the subiaArray to be sorted
* int right - end index of the subiaArray to be sorted
*RETURNS : no value
******************************************************************************/
void fnMerge(int a[], int low,int mid,int high)
{
int i,k,j,b[500000];
i=k=low;
j=mid+1;
while(i<=mid && j<=high)
{
if(a[i]<a[j])
b[k++]=a[i++];
else
b[k++]=a[j++];
}
while(i<=mid)
b[k++]=a[i++];
while(j<=high)
b[k++]=a[j++];
for(i=low;i<k;i++)
a[i]=b[i];
}
/******************************************************************************
*Function : fnMergeSort
*Description : Function to sort elements in an iaArray using Merge Sort
*Function parameters:
* int a[] - iaArray to hold integers
* int low - start index of the array to be sorted
* int high- end index of the array to be sorted
*RETURNS : no value
******************************************************************************/
void fnMergeSort(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
fnMergeSort(a,low,mid);
fnMergeSort(a,mid+1,high);
fnMerge(a,low,mid,high);
}
}
/******************************************************************************
*Function : GenRandInput
*Description : Function to generate a fixed number of random elements
*Function parameters:
* int X[] - array to hold integers
* int n - no of elements in the array
*RETURNS :no return value
******************************************************************************/
void fnGenRandInput(int X[], int n)
{
int i;
srand(time(NULL));
for(i=0;i<n;i++)
{
X[i] = rand()%10000;
}
}
/******************************************************************************
*Function : DispArray
*Description : Function to display elements of an array
*Function parameters:
* int X[] - array to hold integers
* int n - no of elements in the array
*RETURNS : no return value
******************************************************************************/
void fnDispArray( int X[], int n)
{
int i;
for(i=0;i<n;i++)
printf(" %5d \n",X[i]);
}Output
1.MergeSort
2.Plot the Graph
3.Exit
Enter your choice
1
Enter number of elements to sort : 6
Unsorted Array
4680
2144
465
5406
8471
3602
Sorted Array
465
2144
3602
4680
5406
8471
1.MergeSort
2.Plot the Graph
3.Exit
Enter your choice
2
Data File generated and stored in file < MergePlot.dat >.
Use a plotting utility
1.MergeSort
2.Plot the Graph
3.Exit
Enter your choice
3
Plotting Script for Gnuplot
We will now see how to generate a plot graph of data contained in MergePlot.dat and store it as an image. For that let’s write a gnuplot script file called 03MergePlot.gpl. The contents of which are shown below
# Gnuplot script file for plotting data in file "MergePlot.dat"
# This file is called MergePlot.gpl
set terminal png font arial
set title "Time Complexity for Merge Sort"
set autoscale
set xlabel "Size of Input"
set ylabel "Sorting Time (microseconds)"
set grid
set output "MergePlot.png"
plot "MergePlot.dat" t 'Merge Sort' with linesTo execute the Gnuplot script you have to give the following command:
$ gnuplot 03MergePlot.gplYou can now see that an image file by name MergePlot.png containing the graph will be created in your local folder.
Time Complexity Analysis of Merge Sort
Worst Case – O(n*log n)
Average Case – O(n*log n)
Best Case – O(n*log n)
Program 12
N Queen’s problem
Design and implement C/C++ Program for N Queen’s problem using Backtracking.
C++ Code
/******************************************************
*File : 12NQueens.cpp
*Description: Program to solve N Queens problem using backtracking.
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************/
#include <iostream>
#include <cstdlib>
using namespace std;
const int MAX = 10;
int SolnCount =0;
void fnChessBoardShow(int n, int colVec[MAX]);
bool fnCheckPlace(int KthQueen, int ColNum, int colVec[MAX]);
int NQueen(int k,int n, int colVec[MAX]);
/******************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************/
int main(void)
{
int n;
int colVec[MAX];
cout << "Enter the number of queens : ";
cin >> n;
if (!NQueen(0,n,colVec))
cout << "No solution exists for the given problem instance." << endl;
else
cout << "Number of solution for the given problem instance is : "
<< SolnCount << endl;
return 0;
}
/******************************************************
*Function : NQueen
*Description : Function to place n queens on a nxn chess board without any
* queen attacking any other queen
*Input parameters:
* int k - kth queen
* int n - no of queens
* int colVec[MAX] - vector containing column numbers of each queen
*RETURNS : returns 1 if solution exists or zero otherwise
******************************************************/
int NQueen(int k,int n, int colVec[MAX])
{
static int flag;
for(int i=0; i<n; i++)
{
if(fnCheckPlace(k,i,colVec) == true)
{
colVec[k] = i;
if(k == n-1)
{
fnChessBoardShow(n,colVec);
SolnCount++;
flag = 1;
return flag;
}
NQueen(k+1, n, colVec);
}
}
return flag;
}
/******************************************************
*Function : fnCheckPlace
*Description: Function to check whether a kth queen can be placed in a specific
* column or not
*Input parameters:
* int KthQueen - kth queen
* int ColNum - columnn number
* int colVec[MAX] - vector containing column numbers of each queen
*RETURNS : returns true if the queen can be palced or false otherwise
******************************************************/
bool fnCheckPlace(int KthQueen, int ColNum, int colVec[MAX])
{
for(int i=0; i<KthQueen; i++)
{
if(colVec[i] == ColNum || abs(colVec[i]-ColNum) == abs(i-KthQueen))
return false;
}
return true;
}
/******************************************************
*Function : fnChessBoardShow
*Description: Function to graphically display solution to n queens problem
*Input parameters:
* int n - no of queens
* int colVec[MAX] - vector containing column numbers of each queen
*RETURNS : no value
******************************************************/
void fnChessBoardShow(int n, int colVec[MAX])
{
cout << "nSolution #" << SolnCount+1 << endl << endl;
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
if (j == colVec[i])
cout << "Q ";
else
cout << "# ";
}
cout << endl;
}
cout << endl;
}C Code
/******************************************************
*File : 12NQueens.cpp
*Description: Program to solve N Queens problem using backtracking.
*Author : Prabodh C P
*Compiler : g++ compiler 11.4.0, Ubuntu 22.04
*Date : 31 Mar 2024
******************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
const int MAX = 10;
int SolnCount =0;
void fnChessBoardShow(int n, int colVec[MAX]);
bool fnCheckPlace(int KthQueen, int ColNum, int colVec[MAX]);
int NQueen(int k,int n, int colVec[MAX]);
/******************************************************
*Function : main
*Input parameters: no parameters
*RETURNS : 0 on success
******************************************************/
int main(void)
{
int n;
int colVec[MAX];
printf("Enter the number of queens : ");
scanf("%d", &n);
if (!NQueen(0,n,colVec))
printf("No solution exists for the given problem instance.n");
else
printf("Number of solution for the given problem instance is : %dn", SolnCount);
return 0;
}
/******************************************************
*Function : NQueen
*Description : Function to place n queens on a nxn chess board without any
* queen attacking any other queen
*Input parameters:
* int k - kth queen
* int n - no of queens
* int colVec[MAX] - vector containing column numbers of each queen
*RETURNS : returns 1 if solution exists or zero otherwise
******************************************************/
int NQueen(int k,int n, int colVec[MAX])
{
static int flag;
for(int i=0; i<n; i++)
{
if(fnCheckPlace(k,i,colVec) == true)
{
colVec[k] = i;
if(k == n-1)
{
fnChessBoardShow(n,colVec);
SolnCount++;
flag = 1;
return flag;
}
NQueen(k+1, n, colVec);
}
}
return flag;
}
/******************************************************
*Function : fnCheckPlace
*Description: Function to check whether a kth queen can be placed in a specific
* column or not
*Input parameters:
* int KthQueen - kth queen
* int ColNum - columnn number
* int colVec[MAX] - vector containing column numbers of each queen
*RETURNS : returns true if the queen can be palced or false otherwise
******************************************************/
bool fnCheckPlace(int KthQueen, int ColNum, int colVec[MAX])
{
for(int i=0; i<KthQueen; i++)
{
if(colVec[i] == ColNum || abs(colVec[i]-ColNum) == abs(i-KthQueen))
return false;
}
return true;
}
/******************************************************
*Function : fnChessBoardShow
*Description: Function to graphically display solution to n queens problem
*Input parameters:
* int n - no of queens
* int colVec[MAX] - vector containing column numbers of each queen
*RETURNS : no value
******************************************************/
void fnChessBoardShow(int n, int colVec[MAX])
{
printf("nSolution #%dnn", SolnCount+1);
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
if (j == colVec[i])
printf("Q ");
else
printf("# ");
}
printf("n");
}
printf("n");
}Output
Enter the number of queens : 3
No solution exists for the given problem instance.
Enter the number of queens : 4
Solution #1
# Q # #
# # # Q
Q # # #
# # Q #
Solution #2
# # Q #
Q # # #
# # # Q
# Q # #
Number of solution for the given problem instance is : 2Additional solutions
Travelling Sales Person Problem
Write C++/ Java programs to solve Travelling Sales Person problem using Dynamic programming.
C++ Code
#include<iostream>
#include<iomanip>
using namespace std;
int cities[10][10],completed[10],n,cost=0;
void takeInput();
int least(int );
void mincost(int);
int main()
{
takeInput();
cout << "nnThe Path is:n";
mincost(0); //passing 0 because starting vertex
cout << "nnMinimum cost is " << cost << endl;
return 0;
}
void takeInput()
{
int i,j;
cout << "Enter the number of cities: ";
cin >> n;
cout << "nEnter the Cost Matrixn";
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cin >> cities[i][j];
completed[i]=0;
}
cout << "nnThe cost list is:";
for( i=0;i < n;i++)
{
cout << endl;
for(j=0;j < n;j++)
cout << "t" << cities[i][j];
}
}
int least(int c)
{
int i,nc=999;
int min=999,kmin;
for(i=0;i < n;i++)
{
if((cities[c][i]!=0)&&(completed[i]==0))
{
if(cities[c][i]+cities[i][c] < min)
{
min=cities[i][0]+cities[c][i];
kmin=cities[c][i];
nc=i;
}
}
}
if(min!=999)
cost+=kmin;
return nc;
}
void mincost(int city)
{
int ncity;
completed[city]=1;
cout << city << "--->";
ncity=least(city);
if(ncity==999)
{
ncity=0;
cout << ncity;
cost+=cities[city][ncity];
return;
}
mincost(ncity);
}
Java Code
import java.util.Scanner;
public class TravelingSalesmanProblem {
private static int[][] cities;
private static int[] completed;
private static int n;
private static int cost;
public static void main(String[] args) {
takeInput();
System.out.println("nnThe Path is:");
minCost(0); // Start from vertex 0
System.out.println("nnMinimum cost is " + cost);
}
private static void takeInput() {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of cities: ");
n = scanner.nextInt();
cities = new int[n][n];
completed = new int[n];
System.out.println("nEnter the Cost Matrix");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cities[i][j] = scanner.nextInt();
completed[i] = 0;
}
System.out.println("nnThe cost list is:");
for (int i = 0; i < n; i++) {
System.out.println();
for (int j = 0; j < n; j++)
System.out.print("t" + cities[i][j]);
}
}
private static int least(int c) {
int nc = 999;
int min = 999;
int kmin = 0;
for (int i = 0; i < n; i++) {
if (cities[c][i] != 0 && completed[i] == 0) {
if (cities[c][i] + cities[i][c] < min) {
min = cities[i][0] + cities[c][i];
kmin = cities[c][i];
nc = i;
}
}
}
if (min != 999)
cost += kmin;
return nc;
}
private static void minCost(int city) {
completed[city] = 1;
System.out.print(city + "--->");
int ncity = least(city);
if (ncity == 999) {
ncity = 0;
System.out.print(ncity);
cost += cities[city][ncity];
return;
}
minCost(ncity);
}
}
Input Graph
For this program lets consider the following graph
Output
Enter the number of cities: 5
Enter the Cost Matrix
0 3 1 7 9
3 0 4 2 5
1 4 0 5 6
7 2 5 0 4
9 5 6 4 0
The cost list is:
0 3 1 7 9
3 0 4 2 5
1 4 0 5 6
7 2 5 0 4
9 5 6 4 0
The Path is:
0--->2--->1--->3--->4--->0
Minimum cost is 20
Minimum Cost Tour
Hamiltonian Cycles
Design and implement C++/Java Program to find all Hamiltonian Cycles in a connected undirected Graph G of n vertices using backtracking principle.
C++ Code
/* C++ program for solution of Hamiltonian
Cycle problem using backtracking */
#include <bits/stdc++.h>
using namespace std;
// Number of vertices in the graph
#define V 5
void printSolution(int path[]);
/* A utility function to check if
the vertex v can be added at index 'pos'
in the Hamiltonian Cycle constructed
so far (stored in 'path[]') */
bool isSafe(int v, bool graph[V][V],
int path[], int pos)
{
/* Check if this vertex is an adjacent
vertex of the previously added vertex. */
if (graph [path[pos - 1]][ v ] == 0)
return false;
/* Check if the vertex has already been included.
This step can be optimized by creating
an array of size V */
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
/* A recursive utility function
to solve hamiltonian cycle problem */
bool hamCycleUtil(bool graph[V][V],
int path[], int pos)
{
/* base case: If all vertices are
included in Hamiltonian Cycle */
if (pos == V)
{
// And if there is an edge from the
// last included vertex to the first vertex
if (graph[path[pos - 1]][path[0]] == 1)
return true;
else
return false;
}
// Try different vertices as a next candidate
// in Hamiltonian Cycle. We don't try for 0 as
// we included 0 as starting point in findHamCycle()
for (int v = 1; v < V; v++)
{
/* Check if this vertex can be added
// to Hamiltonian Cycle */
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
/* recur to construct rest of the path */
if (hamCycleUtil (graph, path, pos + 1) == true)
return true;
/* If adding vertex v doesn't lead to a solution,
then remove it */
path[pos] = -1;
}
}
/* If no vertex can be added to
Hamiltonian Cycle constructed so far,
then return false */
return false;
}
/* This function solves the Hamiltonian Cycle problem
using Backtracking. It mainly uses hamCycleUtil() to
solve the problem. It returns false if there is no
Hamiltonian Cycle possible, otherwise return true
and prints the path. Please note that there may be
more than one solutions, this function prints one
of the feasible solutions. */
bool findHamCycle(bool graph[V][V])
{
int *path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
/* Let us put vertex 0 as the first vertex in the path.
If there is a Hamiltonian Cycle, then the path can be
started from any point of the cycle as the graph is undirected */
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false )
{
cout << "nSolution does not exist for this graph" << endl;
return false;
}
printSolution(path);
return true;
}
/* A utility function to print solution */
void printSolution(int path[])
{
cout << "Solution Exists:"
" Following is one Hamiltonian Cycle n";
for (int i = 0; i < V; i++)
cout << path[i] << " ";
// Let us print the first vertex again
// to show the complete cycle
cout << path[0] << " ";
cout << endl;
}
// Driver Code
int main()
{
int iNum;
bool g1[V][V], g2[V][V];
cout << "nEnter the number of nodes in the first graph : ";
cin >> iNum;
cout << "nEnter the adjacency matrix of the first graph" << endl;
for(int i=0; i<iNum; i++)
{
for(int j=0; j<iNum; j++)
{
cin >> g1[i][j];
}
}
// Print the solution
findHamCycle(g1);
cout << "nEnter the number of nodes in the second graph : ";
cin >> iNum;
cout << "nEnter the adjacency matrix of the second graph" << endl;
for(int i=0; i<iNum; i++)
{
for(int j=0; j<iNum; j++)
{
cin >> g2[i][j];
}
}
// Print the solution
findHamCycle(g2);
return 0;
}
Java Code
import java.util.Scanner;
class HamiltonianCycle {
private static final int V = 5;
private static boolean isSafe(int v, int[][] graph, int[] path, int pos) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; i++) {
if (path[i] == v)
return false;
}
return true;
}
private static boolean hamCycleUtil(int[][] graph, int[] path, int pos) {
if (pos == V) {
if (graph[path[pos - 1]][path[0]] == 1)
return true;
else
return false;
}
for (int v = 1; v < V; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1) == true)
return true;
path[pos] = -1;
}
}
return false;
}
private static boolean findHamCycle(int[][] graph) {
int[] path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false) {
System.out.println("nSolution does not exist for this graph");
return false;
}
printSolution(path);
return true;
}
private static void printSolution(int[] path) {
System.out.print("Solution Exists: Following is one Hamiltonian Cycle n");
for (int i = 0; i < V; i++)
System.out.print(path[i] + " ");
System.out.print(path[0] + " ");
System.out.println();
}
public static void main(String[] args) {
int iNum;
int[][] g1 = new int[V][V];
int[][] g2 = new int[V][V];
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of nodes in the first graph: ");
iNum = scanner.nextInt();
System.out.println("Enter the adjacency matrix of the first graph:");
for (int i = 0; i < iNum; i++) {
for (int j = 0; j < iNum; j++) {
g1[i][j] = scanner.nextInt();
}
}
findHamCycle(g1);
System.out.print("Enter the number of nodes in the second graph: ");
iNum = scanner.nextInt();
System.out.println("Enter the adjacency matrix of the second graph:");
for (int i = 0; i < iNum; i++) {
for (int j = 0; j < iNum; j++) {
g2[i][j] = scanner.nextInt();
}
}
findHamCycle(g2);
}
}
Input Graphs
Let us consider the following graphs as input for this program
Graph 1
Graph 2
Output
Enter the number of nodes in the first graph : 5
Enter the adjacency matrix of the first graph
0 1 0 1 0
1 0 1 1 1
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
Solution Exists: Following is one Hamiltonian Cycle
0 1 2 4 3 0
Enter the number of nodes in the second graph : 5
Enter the adjacency matrix of the second graph
0 1 0 1 0
1 0 1 1 1
0 1 0 0 1
1 1 0 0 0
0 1 1 0 0
Solution does not exist for this graph
If you are also looking for other Lab Manuals, head over to my following blog :
Prabodh C P
Prabodh C P is a faculty in the Dept of CSE SIT, Tumkur and also currently a Research Scholar pursuing PhD in IIT Hyderabad. He conducts online classes for C, C++, Python. For more info call +919392302100
