Demystifying Algorithms & Solving Problems
In this blog post, you will find solutions for the lab component Design & Analysis of Algorithms (21CS42) course work for the IV semester of VTU university. The solutions to the lab component are coded in 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 here. Along with C++ programs for each question I have provided an equivalent Java Program as well.
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.
Module 1
Selection Sort
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. Demonstrate using C++/Java how the brute force method works along with its time complexity analysis: worst case, average case and best case.
C++ Code
/******************************************************************************
*File : 01SelectionSort.cpp
*Description : Program to sort an array using Merge Sort
*Author: Prabodh C P
*Compiler: gcc compiler 7.5.0, Ubuntu 18.04
*Date: Friday 4 February 2020
******************************************************************************/
#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 fnSortArray(int);
void fnDispArray(int);
void fnSwap(int &,int &);
};
int main( int argc, char **argv)
{
struct timespec tv;
int iChoice, i, iNum;
double dStart, dEnd;
SelectionSort myListObj;
ofstream fout("SelectPlot.dat", ios::out);
for(;;)
{
cout << "\n1.Plot the Graph\n2.SelectionSort\n3.Exit" ;
cout << "\nEnter your choice\n";
cin >> iChoice;
switch(iChoice)
{
case 1: for(i=100;i<10000;i+=100)
{
myListObj.fnGenRandArray(i);
clock_gettime(CLOCK_REALTIME, &tv);
dStart = tv.tv_sec + tv.tv_nsec/1000000000.0;
myListObj.fnSortArray(i);
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 < SelectPlot.dat >.\n Use a plotting utility\n";
break;
case 2:
cout << "\nEnter number of elements to sort : "; cin >> iNum;
myListObj.fnGenRandArray(iNum);
cout << "\nUnsorted Array" << endl;
myListObj.fnDispArray(iNum);
myListObj.fnSortArray(iNum);
cout << "\nSorted Array" << endl;
myListObj.fnDispArray(iNum);
break;
case 3:
exit(0);
}
}
fout.close();
return 0;
}
void SelectionSort::fnGenRandArray(int n)
{
int i, iVal;
srand(time(NULL));
for(i=0;i<n;i++)
{
iVal = rand()%10000;
numList.push_back(iVal);
}
}
void SelectionSort::fnDispArray(int n)
{
int i;
for(i=0;i<n;i++)
{
cout << setw(8) << numList[i] << endl;
}
}
void SelectionSort::fnSortArray(int n)
{
int i, j, min_idx;
for(i=0;i<n-1;i++)
{
min_idx = i;
for(j=i+1;j<n;j++)
{
if(numList[j] < numList[min_idx])
min_idx = j;
}
fnSwap(numList[i], numList[min_idx]);
}
}
void SelectionSort::fnSwap(int &a,int &b)
{
int t;
t = a; a = b; b = t;
}
Java Code
import java.util.ArrayList;
import java.util.List;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
public class SelectionSort {
private List<Integer> numList;
public SelectionSort() {
numList = new ArrayList<>();
}
public void fnGenRandArray(int n) {
int i, iVal;
for (i = 0; i < n; i++) {
iVal = (int) (Math.random() * 10000);
numList.add(iVal);
}
}
public void fnDispArray(int n) {
for (int i = 0; i < n; i++) {
System.out.println(String.format("%8d", numList.get(i)));
}
}
public void fnSortArray(int n) {
int i, j, min_idx;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++) {
if (numList.get(j) < numList.get(min_idx))
min_idx = j;
}
fnSwap(i, min_idx);
}
}
public void fnSwap(int a, int b) {
int temp = numList.get(a);
numList.set(a, numList.get(b));
numList.set(b, temp);
}
public static void main(String[] args) {
long startTime, endTime;
int iChoice, iNum;
SelectionSort myListObj = new SelectionSort();
try (PrintWriter fout = new PrintWriter(new FileWriter("SelectPlot.dat"))) {
for (;;) {
System.out.println("\n1.SelectionSort\n2.Plot the Graph\n3.Exit");
System.out.println("Enter your choice");
iChoice = Integer.parseInt(System.console().readLine());
switch (iChoice) {
case 1:
System.out.print("Enter number of elements to sort : ");
iNum = Integer.parseInt(System.console().readLine());
myListObj.fnGenRandArray(iNum);
System.out.println("\nUnsorted Array");
myListObj.fnDispArray(iNum);
myListObj.fnSortArray(iNum);
System.out.println("\nSorted Array");
myListObj.fnDispArray(iNum);
break;
case 2:
for (int i = 100; i < 10000; i += 100) {
myListObj.fnGenRandArray(i);
startTime = System.nanoTime();
myListObj.fnSortArray(i);
endTime = System.nanoTime();
// System.out.println(i + "\t" + (endTime - startTime));
fout.println(i + "\t" + ((endTime - startTime) / 1e9));
}
System.out.println("\nData File generated and stored in file < SelectPlot.dat >. Use a plotting utility");
break;
case 3:
System.exit(0);
}
}
} catch (IOException e) {
System.out.println("Error: " + e.getMessage());
}
}
}
Output
1.SelectionSort
2.Plot the Graph
3.Exit
Enter your choice
1
Enter number of elements to sort : 4
Unsorted Array
2465
1009
9680
8206
Sorted Array
1009
2465
8206
9680
1.SelectionSort
2.Plot the Graph
3.Exit
Enter your choice
2
Data File generated and stored in file < SelectPlot.dat >.
Use a plotting utility
1.SelectionSort
2.Plot the Graph
3.Exit
Enter your choice
3
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 SelectPlot.dat
100 0.0001306533813
200 0.0004434585571
300 0.0009500980377
400 0.001492977142
500 0.002258777618
600 0.003211975098
700 0.004380464554
800 0.005626916885
900 0.006759643555
1000 0.005615472794
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 "SelectPlot.dat"
# This file is called 01SelectPlot.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 "SelectPlot.png"
plot "SelectPlot.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.
Time Complexity Analysis
Worst Case – O(n2)
Average Case – O(n2)
Best Case – O(n2)
Module 2
Quick Sort
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. Demonstrate using C++/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case.
C++ Code
/******************************************************************************
*File : 03QuickSort.c
*Description : Program to sort an array using Quick Sort
*Author : Prabodh C P
*Compiler : gcc compiler 7.5.0, Ubuntu 18.04
*Date : Friday 4 February 2020
******************************************************************************/
#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);
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 Sort\n2.Plot the Graph\n3.Exit" ;
cout << "\nEnter your choice\n";
cin >> iChoice;
switch(iChoice)
{
case 1:
cout << "\nEnter number of elements to sort : "; cin >> iNum;
myListObj.fnGenRandArray(iNum);
cout << "\nUnsorted Array" << endl;
myListObj.fnDispArray(iNum);
myListObj.fnQuickSort(0,iNum-1);
cout << "\nSorted Array" << endl;
myListObj.fnDispArray(iNum);
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 utility\n";
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;
srand(time(NULL));
for(i=0;i<n;i++)
{
iVal = rand()%10000;
numList.push_back(iVal);
}
}
void QuickSort::fnDispArray(int n)
{
int i;
for(i=0;i<n;i++)
{
cout << setw(8) << numList[i] << endl;
}
}
void QuickSort::fnSwap(int &a,int &b)
{
int t;
t = a;
a = b;
b = t;
}Java Code
import java.util.ArrayList;
import java.util.List;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
public class QuickSort {
private List<Integer> numList;
public QuickSort() {
numList = new ArrayList<>();
}
public void fnGenRandArray(int n) {
int i, iVal;
for (i = 0; i < n; i++) {
iVal = (int) (Math.random() * 10000);
numList.add(iVal);
}
}
public void fnDispArray(int n) {
for (int i = 0; i < n; i++) {
System.out.println(String.format("%8d", numList.get(i)));
}
}
public void fnSortArray(int l, int r) {
if (l < r) {
int s = fnPartition(l, r);
fnSortArray(l, s - 1);
fnSortArray(s + 1, r);
}
}
public int fnPartition(int l, int r) {
int pivot = numList.get(l);
int i = l + 1;
int j = r;
while (i <= j) {
if (numList.get(i) <= pivot) {
i++;
} else if (numList.get(j) > pivot) {
j--;
} else {
int temp = numList.get(i);
numList.set(i, numList.get(j));
numList.set(j, temp);
i++;
j--;
}
}
int temp = numList.get(l);
numList.set(l, numList.get(j));
numList.set(j, temp);
return j;
}
public static void main(String[] args) {
long startTime, endTime;
int iChoice, iNum;
QuickSort myListObj = new QuickSort();
try (PrintWriter fout = new PrintWriter(new FileWriter("QuickPlot.dat"))) {
for (;;) {
System.out.println("\n1.Quick Sort\n2.Plot the Graph\n3.Exit");
System.out.println("Enter your choice");
iChoice = Integer.parseInt(System.console().readLine());
switch (iChoice) {
case 1:
System.out.print("Enter number of elements to sort : ");
iNum = Integer.parseInt(System.console().readLine());
myListObj.fnGenRandArray(iNum);
System.out.println("\nUnsorted Array");
myListObj.fnDispArray(iNum);
myListObj.fnSortArray(0, iNum - 1);
System.out.println("\nSorted Array");
myListObj.fnDispArray(iNum);
break;
case 2:
for (int i = 100; i < 100000; i += 100) {
myListObj.fnGenRandArray(i);
startTime = System.nanoTime();
myListObj.fnSortArray(0, i - 1);
endTime = System.nanoTime();
fout.println(i + "\t" + ((endTime - startTime) / 1e9));
}
System.out.println("\nData File generated and stored in file < QuickPlot.dat >. Use a plotting utility");
break;
case 3:
System.exit(0);
}
}
} catch (IOException e) {
System.out.println("Error: " + e.getMessage());
}
}
}
Output
1.Quick Sort
2.Plot the Graph
3.Exit
Enter your choice
1
Enter number of elements to sort : 5
Unsorted Array
2828
710
6721
2947
8353
Sorted Array
710
2828
2947
6721
8353
1.Quick Sort
2.Plot the Graph
3.Exit
Enter your choice
2
Data File generated and stored in file < QuickPlot.dat >.
Use a plotting utility
1.Quick Sort
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
# Gnuplot script file for plotting data in file "QuickPlot.dat"
# This file is called 03QuickPlot.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 linesTo execute the Gnuplot script you have to give the following command:
$ 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)
Merge Sort
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. Demonstrate using C++/Java how the divide-and-conquer method works along with its time complexity analysis: worst case, average case and best case.
C++ Code
/******************************************************************************
*File : 03MergeSort.cpp
*Description : Program to sort an array using Merge Sort
*Author: Prabodh C P
*Compiler: gcc compiler 7.5.0, Ubuntu 18.04
*Date: Friday 4 February 2020
******************************************************************************/
#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(int);
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.MergeSort\n2.Plot the Graph\n3.Exit" ;
cout << "\nEnter your choice\n";
cin >> iChoice;
switch(iChoice)
{
case 1:
cout << "\nEnter number of elements to sort : "; cin >> iNum;
myListObj.fnGenRandArray(iNum);
cout << "\nUnsorted Array" << endl;
myListObj.fnDispArray(iNum);
myListObj.fnSortArray(0,iNum-1);
cout << "\nSorted Array" << endl;
myListObj.fnDispArray(iNum);
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 utility\n";
break;
case 3:
exit(0);
}
}
fout.close();
return 0;
}
void MergeSort::fnGenRandArray(int n)
{
int i, iVal;
srand(time(NULL));
for(i=0;i<n;i++)
{
iVal = rand()%10000;
numList.push_back(iVal);
}
}
void MergeSort::fnDispArray(int n)
{
int i;
for(i=0;i<n;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++;
}
}
Java Code
//MergeSort.java
import java.util.ArrayList;
import java.util.List;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
public class MergeSort {
private List<Integer> numList;
public MergeSort() {
numList = new ArrayList<>();
}
public void fnGenRandArray(int n) {
int i, iVal;
for (i = 0; i < n; i++) {
iVal = (int) (Math.random() * 10000);
numList.add(iVal);
}
}
public void fnDispArray(int n) {
for (int i = 0; i < n; i++) {
System.out.println(String.format("%8d", numList.get(i)));
}
}
public void fnSortArray(int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
fnSortArray(low, mid);
fnSortArray(mid + 1, high);
fnMerge(low, mid, high);
}
}
public void fnMerge(int low, int mid, int high) {
List<Integer> b = new ArrayList<>();
int i = low;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= high) {
if (numList.get(i) < numList.get(j))
b.add(numList.get(i++));
else
b.add(numList.get(j++));
}
while (i <= mid)
b.add(numList.get(i++));
while (j <= high)
b.add(numList.get(j++));
for (i = low; i <= high; i++) {
numList.set(i, b.get(k));
k++;
}
}
public static void main(String[] args) {
long startTime, endTime;
int iChoice, iNum;
MergeSort myListObj = new MergeSort();
try (PrintWriter fout = new PrintWriter(new FileWriter("MergePlot.dat"))) {
for (;;) {
System.out.println("\n1.MergeSort\n2.Plot the Graph\n3.Exit");
System.out.println("Enter your choice");
iChoice = Integer.parseInt(System.console().readLine());
switch (iChoice) {
case 1:
System.out.print("Enter number of elements to sort : ");
iNum = Integer.parseInt(System.console().readLine());
myListObj.fnGenRandArray(iNum);
System.out.println("\nUnsorted Array");
myListObj.fnDispArray(iNum);
myListObj.fnSortArray(0, iNum - 1);
System.out.println("\nSorted Array");
myListObj.fnDispArray(iNum);
break;
case 2:
for (int i = 100; i < 100000; i += 100) {
myListObj.fnGenRandArray(i);
startTime = System.nanoTime();
myListObj.fnSortArray(0, i - 1);
endTime = System.nanoTime();
fout.println(i + "\t" + ((endTime - startTime) / 1e9));
}
System.out.println("\nData File generated and stored in file < MergePlot.dat >. Use a plotting utility");
break;
case 3:
System.exit(0);
}
}
} catch (IOException e) {
System.out.println("Error: " + e.getMessage());
}
}
}
Output
Enter a number : 5nfn(5) = 31.MergeSort
2.Plot the Graph
3.Exit
Enter your choice
1
Enter number of elements to sort : 4
Unsorted Array
6356
627
4088
4843
Sorted Array
627
4088
4843
6356
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 03MergePlot.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)
Module 3
Knapsack problem using Greedy method.
Write & Execute C++/Java Program to solve Knapsack problem using Greedy method.
C++ Code
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef struct{
int profit;
int weight;
float profitRatio;
float fraction;
}Item;
int main()
{
vector <Item> itemList;
int iNum, i, pos;
float knCap, remCap, totProfit;
Item a;
cout << "Enter the number of items : " ;
cin >> iNum;
cout << "Enter Knapsack capacity : ";
cin >> knCap;
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
{
pos=0;
while(a.profitRatio < itemList[pos].profitRatio) pos++;
itemList.insert(itemList.begin() + pos,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;
}
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 << "\nKNAPSACK SOLUTION\n";
cout << "Item\tWeight\tProfit\tFraction Chosen\n";
for(i=0;i<iNum;i++)
{
cout << i+1 << "\t" << itemList[i].weight << "\t" << itemList[i].profit << "\t" << itemList[i].fraction << endl;
}
cout << "\nTotal Profit Earned : " << totProfit << endl;
return 0;
}
Java Code
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
class Item {
int profit;
int weight;
float profitRatio;
float fraction;
}
public class KnapsackProblem {
public static void main(String[] args) {
List<Item> itemList = new ArrayList<>();
int iNum, i;
float knCap, remCap, totProfit;
Item a;
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of items: ");
iNum = scanner.nextInt();
System.out.print("Enter Knapsack capacity: ");
knCap = scanner.nextFloat();
for (i = 0; i < iNum; i++) {
a = new Item();
System.out.print("Enter profit: ");
a.profit = scanner.nextInt();
System.out.print("Enter weight: ");
a.weight = scanner.nextInt();
a.profitRatio = (float) a.profit / a.weight;
a.fraction = 0.0f;
itemList.add(a);
}
itemList.sort(Comparator.comparing((Item item) -> item.profitRatio).reversed());
remCap = knCap;
totProfit = 0.0f;
for (i = 0; i < iNum; i++) {
a = itemList.get(i);
if (a.weight < remCap) {
a.fraction = 1.0f;
remCap -= a.weight;
totProfit += a.profit;
} else {
a.fraction = remCap / a.weight;
remCap = 0;
totProfit += a.profit * a.fraction;
break;
}
}
System.out.println("\nKNAPSACK SOLUTION");
System.out.println("Item\tWeight\tProfit\tFraction Chosen");
for (i = 0; i < iNum; i++) {
a = itemList.get(i);
System.out.printf("%d\t%d\t%d\t%.2f\n", i + 1, a.weight, a.profit, a.fraction);
}
System.out.println("\nTotal Profit Earned: " + totProfit);
scanner.close();
}
}
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 : 5
Enter Knapsack capacity : 60
Enter profit : 30
Enter weight : 5
Enter profit : 40
Enter weight : 10
Enter profit : 45
Enter weight : 15
Enter profit : 77
Enter weight : 22
Enter profit : 90
Enter weight : 25
KNAPSACK SOLUTION
Item Weight Profit Fraction Chosen
1 5 30 1.00
2 10 40 1.00
3 25 90 1.00
4 22 77 0.91
5 15 45 0.00
Total Profit Earned: 230.0
Dijkstra’s Algorithm
Write & Execute C++/Java Program to find shortest paths to other vertices from a given vertex in a weighted connected graph, using Dijkstra’s algorithm.
C++ Code
/******************************************************************************
*File : 05Dijkstra.cpp
*Description: Program to find shortest paths to other vertices using
* Dijkstra's algorithm.
*Author : Prabodh C P
*Compiler : g++ compiler 7.5.0, Ubuntu 18.04
*Date : 31 Mar 2020
******************************************************************************/
#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 nodes\n";
cin >> n;
cout << "Enter the Cost Matrix\n" << 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;
}
}
}
}
}Java Code
import java.util.Scanner;
public class DijkstraAlgorithm {
private static final int MAXNODES = 10;
private static final int INF = 9999;
public static void main(String[] args) {
int n, cost[][] = new int[MAXNODES][MAXNODES], dist[] = new int[MAXNODES], visited[] = new int[MAXNODES], path[] = new int[MAXNODES], i, j, source, dest;
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of nodes: ");
n = scanner.nextInt();
System.out.println("Enter the Cost Matrix:");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
cost[i][j] = scanner.nextInt();
}
}
System.out.print("Enter the Source vertex: ");
source = scanner.nextInt();
System.out.println("\nShortest paths from Source Vertex " + source + " to other vertices:");
for (dest = 0; dest < n; dest++) {
fnDijkstra(cost, dist, path, visited, source, dest, n);
if (dist[dest] == INF) {
System.out.println(dest + " is not reachable");
} else {
System.out.println();
i = dest;
do {
System.out.print(i + " <-- ");
i = path[i];
} while (i != source);
System.out.println(i + " = " + dist[dest]);
}
}
}
private static void fnDijkstra(int[][] cost, int[] dist, int[] path, int[] visited, int source, int dest, int n) {
int i, j, a, b, min;
for (i = 0; i < n; i++) {
visited[i] = 0;
dist[i] = cost[source][i];
path[i] = source;
}
visited[source] = 1;
for (i = 1; i < n; i++) {
min = INF;
a = -1;
for (j = 0; j < n; j++) {
if (visited[j] == 0 && dist[j] < min) {
min = dist[j];
a = j;
}
}
if (a == -1) {
return;
}
visited[a] = 1;
if (a == dest) {
return;
}
for (b = 0; b < n; b++) {
if (visited[b] == 0 && dist[a] + cost[a][b] < dist[b]) {
dist[b] = dist[a] + cost[a][b];
path[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 = 8Kruskal’s Algorithm
Write & Execute C++/Java Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Kruskal’s algorithm. Use Union-Find algorithms in your program.
C++ Code
/******************************************************************************
*File : 06Kruskal.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 7.5.0, Ubuntu 18.04
*Date : 31 Mar 2020
******************************************************************************/
#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;
}Java Code
import java.util.Scanner;
class Kruskal {
static class Edge {
int u, v, cost;
}
private static final int MAXNODES = 10;
private static final int INF = 9999;
private static int findParent(int v, int[] parent) {
while (parent[v] != v)
v = parent[v];
return v;
}
private static void union(int i, int j, int[] parent) {
if (i < j)
parent[j] = i;
else
parent[i] = j;
}
private static void inputGraph(int m, Edge[] e) {
Scanner scanner = new Scanner(System.in);
for (int k = 0; k < m; k++) {
System.out.println("Enter edge and cost in the form u, v, w :");
int i = scanner.nextInt();
int j = scanner.nextInt();
int cost = scanner.nextInt();
e[k] = new Edge();
e[k].u = i;
e[k].v = j;
e[k].cost = cost;
}
scanner.close();
}
private static int getMinEdge(Edge[] e, int n) {
int small = INF;
int pos = -1;
for (int i = 0; i < n; i++) {
if (e[i].cost < small) {
small = e[i].cost;
pos = i;
}
}
return pos;
}
private static void kruskal(int n, Edge[] e, int m) {
int count = 0;
int k = 0;
int sum = 0;
int[][] t = new int[MAXNODES][2];
int[] parent = new int[MAXNODES];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
while (count != n - 1) {
int pos = getMinEdge(e, m);
if (pos == -1) {
break;
}
int u = e[pos].u;
int v = e[pos].v;
int i = findParent(u, parent);
int j = findParent(v, parent);
if (i != j) {
t[k][0] = u;
t[k][1] = v;
k++;
count++;
sum += e[pos].cost;
union(i, j, parent);
}
e[pos].cost = INF;
}
if (count == n - 1) {
System.out.println("\nSpanning tree exists");
System.out.println("The Spanning tree is shown below");
for (int i = 0; i < n - 1; i++)
System.out.println(t[i][0] + " " + t[i][1]);
System.out.println("Cost of the spanning tree: " + sum);
} else {
System.out.println("\nThe spanning tree does not exist");
}
}
public static void main(String[] args) {
int n = 6, m = 20;
Edge[] e = new Edge[2 * MAXNODES];
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of nodes : ");
n = scanner.nextInt();
System.out.print("Enter the number of edges : ");
m = scanner.nextInt();
inputGraph(m, e);
kruskal(n, e, m);
}
}
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
Prim’s Algorithm
Write & Execute C++/Java Program to find Minimum Cost Spanning Tree of a given connected undirected graph using Prim’s algorithm.
C++ Code
/******************************************************************************
*File : 07PrimMST.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 7.5.0, Ubuntu 18.04
*Date : 31 Mar 2020
******************************************************************************/
#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 exist\n";
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];
}Java Code
import java.util.Scanner;
class Prims {
static final int MAXNODES = 10;
static void fnPrims(int n, int[][] cost) {
int i, j, u, v, min;
int sum, k, t[][] = new int[MAXNODES][2], p[] = new int[MAXNODES], d[] = new int[MAXNODES], s[] = new int[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)
System.out.println("\nSpanning tree does not exist");
else {
System.out.println("\nThe spanning tree exists and the minimum cost spanning tree is:");
for (i = 0; i < k; i++)
System.out.println(t[i][1] + " " + t[i][0]);
System.out.println("\nThe cost of the minimum cost spanning tree is " + sum);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a[][] = { { 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;
System.out.print("Enter the number of vertices: ");
n = scanner.nextInt();
fnGetMatrix(n, a);
fnPrims(n, a);
}
static void fnGetMatrix(int n, int a[][]) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the Cost Adjacency Matrix:");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
a[i][j] = scanner.nextInt();
scanner.close();
}
}
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
Module 4
Floyd’s Algorithm
Write C++/ Java programs to solve All-Pairs Shortest Paths problem using Floyd’s algorithm.
C++ Code
/***************************************************************************
*File : Floyd.c
*Description: Program to implement Floyd's Algorithm
*Author : Prabodh C P
*Compiler : gcc compiler 7.5.0, Ubuntu 18.04
*Date : 31 Mar 2020
***************************************************************************/
#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 ALGORITHM\t*\n";
cout << "*********************************************************";
cout << "\nEnter the number of vertices\n";
cin >> iN;
cout << "\nEnter the Cost adjacency Matrix\n";
for(i=0;i<iN;i++)
for(j=0;j<iN;j++)
cin >> iaCost[i][j];
cout << "\nInput Graph\n";
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 Matrix\n";
for(i=0;i<iN;i++)
{
for(j=0;j<iN;j++)
{
cout << iaFloyd[i][j] << "\t";
}
cout << endl;
}
cout << "\n";
return 0;
}Java Code
import java.util.Scanner;
public class FloydAlgorithm {
public static void main(String[] args) {
int iN, i, j, k;
int[][] iaFloyd = new int[10][10];
int[][] iaCost = new int[10][10];
System.out.println("\n*********************************************************");
System.out.println("*\tPROGRAM TO IMPLEMENT FLOYD'S ALGORITHM\t*");
System.out.println("*********************************************************");
System.out.println("\nEnter the number of vertices");
Scanner scanner = new Scanner(System.in);
iN = scanner.nextInt();
System.out.println("\nEnter the Cost adjacency Matrix");
for (i = 0; i < iN; i++) {
for (j = 0; j < iN; j++) {
iaCost[i][j] = scanner.nextInt();
}
}
System.out.println("\nInput Graph");
for (i = 0; i < iN; i++) {
for (j = 0; j < iN; j++) {
System.out.print(iaCost[i][j] + "\t");
}
System.out.println();
}
System.out.println();
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]);
}
}
}
System.out.println("\nAll Pair Shortest Path Matrix");
for (i = 0; i < iN; i++) {
for (j = 0; j < iN; j++) {
System.out.print(iaFloyd[i][j] + "\t");
}
System.out.println();
}
System.out.println();
}
}
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
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 i,j;
cout << "Enter the number of cities: ";
cin >> n;
cout << "\nEnter the Cost Matrix\n";
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cin >> cities[i][j];
completed[i]=0;
}
cout << "\n\nThe 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);
}
int main()
{
takeInput();
cout << "\n\nThe Path is:\n";
mincost(0); //passing 0 because starting vertex
cout << "\n\nMinimum cost is " << cost << endl;
return 0;
}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("\n\nThe Path is:");
minCost(0); // Start from vertex 0
System.out.println("\n\nMinimum 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("\n\nThe 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
0/1 Knapsack problem
Write C++/ Java programs to solve 0/1 Knapsack problem using Dynamic Programming method.
C++ Code
/********************************************************************************
*File : 10AKnapsack.cpp
*Description: Program to find Binomial Coefficient
*Author : Prabodh C P
*Compiler : g++ compiler 7.5.0, Ubuntu 18.04
*Date : 31 Mar 2020
********************************************************************************/
#include <iostream>
#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 << "\nWeight " << i << ": ";
cin >> weight[i];
}
cout << "\nEnter the profits : \n";
for (i=1; i<=numOfObj; i++)
{
cout << "\nProfit " << 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];
}
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;
}
Java Code
import java.util.Scanner;
class Knapsack {
private int totalProfit;
private int[] weight;
private int[] profit;
private int capacity;
private int numOfObj;
private int[] subset;
private int[][] table;
public Knapsack() {
totalProfit = 0;
}
public void fnReadKnapDetails() {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the maximum number of objects: ");
numOfObj = scanner.nextInt();
weight = new int[numOfObj + 1];
profit = new int[numOfObj + 1];
System.out.println("\nEnter the weights:");
for (int i = 1; i <= numOfObj; i++) {
System.out.print("Weight " + i + ": ");
weight[i] = scanner.nextInt();
}
System.out.println("\nEnter the profits:");
for (int i = 1; i <= numOfObj; i++) {
System.out.print("Profit " + i + ": ");
profit[i] = scanner.nextInt();
}
System.out.print("\nEnter the maximum capacity: ");
capacity = scanner.nextInt();
subset = new int[numOfObj + 1];
table = new int[numOfObj + 1][capacity + 1];
}
private int max(int x, int y) {
return (x > y) ? x : y;
}
public void fnCalcProfit() {
for (int j = 0; j <= capacity; j++)
table[0][j] = 0;
for (int i = 0; i <= numOfObj; i++)
table[i][0] = 0;
for (int i = 1; i <= numOfObj; i++) {
for (int 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];
}
public void fnFindSubSet() {
int i = numOfObj;
int j = capacity;
while (i >= 1 && j >= 1) {
if (table[i][j] != table[i - 1][j]) {
subset[i] = 1;
j = j - weight[i];
}
i--;
}
System.out.print("Items selected for the Knapsack are: ");
for (i = 1; i <= numOfObj; i++) {
if (subset[i] == 1)
System.out.print(i + " ");
}
System.out.println();
System.out.println("Total Profit earned is " + totalProfit);
}
public static void main(String[] args) {
Knapsack knapsackObj = new Knapsack();
knapsackObj.fnReadKnapDetails();
knapsackObj.fnCalcProfit();
knapsackObj.fnFindSubSet();
}
}
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
Items selected for the Knapsack are : 1 2 4
Total Profit earned is 37
Module 5
Subset Sum Problem
Design and implement C++/Java Program to find a subset of a given set S = {S1, S2,…, Sn} of n positive integers whose SUM is equal to a given positive integer d. For example, if S = {1, 2, 5, 6, 8} and d= 9, there are two solutions {1, 2, 6} and {1, 8}. Display a suitable message, if the given problem instance doesn’t have a solution.
C++ Code
/******************************************************
*File : 11SubsetSum.cpp
*Description: Program to solve Subset sum problem.
*Author : Prabodh C P
*Compiler : g++ compiler 7.5.0, Ubuntu 18.04
*Date : 31 Mar 2020
******************************************************/
#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 <<" IS\n{ ";
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;
}Java Code
import java.util.Scanner;
class SubSet {
private static final int MAX = 100;
private int[] stk = new int[MAX];
private int[] set = new int[MAX];
private int size;
private int top;
private int count;
private static int foundSoln = 0;
public SubSet() {
top = -1;
count = 0;
}
public void getInfo() {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the maximum number of elements: ");
size = scanner.nextInt();
System.out.println("Enter the values of the elements: ");
for (int i = 1; i <= size; i++) {
set[i] = scanner.nextInt();
}
}
public void push(int data) {
stk[++top] = data;
}
public void pop() {
top--;
}
public void display() {
System.out.print("\nSOLUTION #" + (++count) + " IS\n{ ");
for (int i = 0; i <= top; i++) {
System.out.print(stk[i] + " ");
}
System.out.println("}");
}
public int findSubset(int pos, int sum) {
if (sum > 0) {
for (int i = pos; i <= size; i++) {
push(set[i]);
foundSoln = findSubset(i + 1, sum - set[i]);
pop();
}
}
if (sum == 0) {
display();
foundSoln = 1;
}
return foundSoln;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int sum;
SubSet set1 = new SubSet();
set1.getInfo();
System.out.print("Enter the sum value: ");
sum = scanner.nextInt();
System.out.println();
if (set1.findSubset(1, sum) == 0) {
System.out.println("The problem instance doesn't have any solution.");
} else {
System.out.println("The above-mentioned sets are the required solution to the given instance.");
}
scanner.close();
}
}
Output
Enter the maximum number of elements : 5
Enter the values of the elements :
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 maximum number of elements : 3
Enter the values of the elements :
3 5 9
Enter the sum value : 6
The problem instance doesnt have any solution.
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
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
