Design & Analysis of Algorithms Lab Manual – 21CS42

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.

  1. Module 1
    1. Selection Sort
  2. Module 2
    1. Quick Sort
    2. Merge Sort
  3. Module 3
    1. Knapsack problem using Greedy method.
    2. Dijkstra’s Algorithm
    3. Kruskal’s Algorithm
    4. Prim’s Algorithm
  4. Module 4
    1. Floyd’s Algorithm
    2. Travelling Sales Person Problem
    3. 0/1 Knapsack problem
  5. Module 5
    1. Subset Sum Problem
    2. Hamiltonian Cycles

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

Plot of Selection Sort

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 lines

To execute the Gnuplot script you have to give the following command:

$ gnuplot 03QuickPlot.gpl

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

To execute the Gnuplot script you have to give the following command:

$ gnuplot 03MergePlot.gpl

You 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

ItemWeightProfit
1530
21040
31545
42277
52590

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

Kruskal’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++