Analysis & Design of Algorithms Lab Manual Final – BCDL404

Prabodh C PApr 19, 2024

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.

BCDL404_Analysis_and_Design_of_Algorithms_Lab Download

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
1. Floyd’s Algorithm
2. Warshall’s Algorithm
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
1. Travelling Sales Person Problem
2. Hamiltonian Cycles

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 = 8

Program 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 gnuplot

After 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 lines

The 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.gpl

You 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(n²)

Average Case – O(n²)

Best Case – O(n²)

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