NIE Institute of Technology, Mysuru

Department of Computer Science and Engineering

DESIGN AND ANALYSIS OF ALGORITHMS

(INTEGRATED)

Course Code : 21CS42

Prepared by :

Mr Gowtham M Ms Sheeban E Tamanna

Asst. Professor Dept of CSE Asst. Professor Dept of CSE
NIEIT, Mysuru NIEIT, Mysuru
Programs
1) 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.

import [Link];
public class selectionSort {

public static void main(String[] args) {

Random random = new Random();
int [] array = new int[10];
for(int i = 0; i<10; i++) {
array[i] = [Link](100);
}
[Link]("The array elements before sorting is");
for (int i = 0; i<10; i++) {
[Link](" "+array[i]);
}
for(int i=0; i<10; i++) {
int minIndex = i;
for(int j=i+1; j<10; j++) {
if(array[j] < array[minIndex]) {
minIndex = j;
}
}
int temp=array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
[Link]("\nThe array elements after swapping is");
for (int i = 0; i<10; i++) {
[Link](" "+array[i]);
}

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

import [Link];
import [Link];

public class qsort

{
 int Partition(int a[],int low,int high)
{
int i,j,temp,key;

key=a[low];
i=low+1;
j=high;

while(true)
{
while(i < high && key >= a[i])
i++;
while(key < a[j])
j--;

if(i<j) // exchange ith and jth elements

{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else // exchange key and jth elements
{
temp=a[low];
a[low]=a[j];
a[j]=temp;
return j; // returns the position of key
}
}//end of while
}//end of Paritition method

void QuickSort(int a[],int low,int high)

{
int j;
if(low<high)
{
j=Partition(a,low,high);
QuickSort(a,low,j-1);
QuickSort(a,j+1,high);
}
}

public static void main(String args[])

{
Random r = new Random();
final int MAX = 10000;
int[] a = new int[MAX];
qsort obj = new qsort();
int n=0,i=0;

Scanner input = new Scanner([Link]);

[Link]("\n Enter the number of elements : ");
n=[Link]();

for(i=0;i<n;i++)
{
a[i] = [Link](1000);//for random number inputs
 [Link]("\n Elements to be sorted \n");
[Link](a[i]+"\t");
}

long stime=0, etime=0;

stime = [Link]();

[Link](a,0,n-1);

etime = [Link]();

[Link]("\n The sorted elements are \n");

for(i=0;i<n;i++)
[Link](a[i]+"\t");

long Tcomplexity = etime - stime;

[Link]("\nTime Complexity for n = " + n + " is: " + (double) Tcomplexity
/ 1000000 + " msec");
[Link]();
}//end of main method
}//end of QSort class

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

import [Link];
import [Link];

public class mergesort {

void msort(int a[], int low, int high)

{
int mid;
if(low<high)
{
mid=(low+high)/2;
msort(a,low,mid); //left array
msort(a,mid+1,high); //right array
merge(a,low,mid,high);
}

void merge(int a[], int low, int mid, int high)

{
int i,j,k;
int[] b=new int[10000];
i=low; //left array with h value low to mid
j=mid+1; //right array with j value mid+1 to high
k=low;
 while((i<=mid) && (j<=high))
{
if(a[i]<a[j]) //compare the elements in subarray and copy smallest element in the array
{
b[k]=a[i];
k=k+1;
i=i+1;
}
else
{
b[k]=a[j];
k=k+1;
j=j+1;
}
}

while(i<=mid)//copy the remaining elements into the new array

{
b[k]=a[i];
k=k+1;
i=i+1;
}

while(j<=high)
{
b[k]=a[j];
k=k+1;
j=j+1;
}

for(i=low;i<=k-1;i++) //copying resultant array into original array

a[i]=b[i];

public static void main(String[] args) {

// TODO Auto-generated method stub
int a[]= new int[100000];
Scanner in = new Scanner([Link]);
long start, end;
mergesort m = new mergesort();

[Link]("MERGE SORT PROGRAM");

[Link]("Enter the number of elements to be sorted");
int n = [Link]();
Random rand= new Random();
for(int i=0;i<n;i++)
a[i]=[Link](100);

[Link]("Array elements to be sorted are");

for(int i=0; i<n; i++)
[Link](a[i]+" ");

start=[Link]();
[Link](a,0,n-1);
end=[Link]();
 [Link]("\nThe sorted elements are");
for(int i=0; i<n; i++)
[Link](a[i]+" ");

[Link]("\nThe time taken to sort is "+(end-start)+"ns");

}

4) To solve Knapsack problem using Greedy method.

import [Link];

public class Lab6B {

public static void main(String[] args) {
float w[]=new float[10],p[]=new float[10];
float ratio[]=new float[10];
Scanner in = new Scanner([Link]);
int i;
[Link]("********* KNAPSACK PROBLEM *******");
[Link]("Enter the total number of items: ");
int n = [Link]();
[Link]("Enter the weight of each item: ");
for(i=1;i<=n;i++)
w[i] = [Link]();
[Link]("Enter the profit of each item: ");
for(i=1;i<=n;i++)
p[i] = [Link]();
[Link]("Enter the knapsack capacity: ");
int m= [Link]();
for(i=1;i<=n;i++)
ratio[i]=p[i]/w[i];
[Link]("Information about knapsack problem are");
[Link]("Capacity = "+m);
displayinfo(n,w,p,ratio);
knapsack(m,n,w,p);
[Link]("*************************************");
}
}
static void displayinfo(int n,float w[],float p[],float ratio[]){
[Link]("ITEM\tWEIGHT\tPROFIT\tRATIO(PROFIT/WEIGHT)");
for(int i=1; i<=n; i++)
[Link](i+"\t"+w[i]+"\t"+p[i]+"\t"+ratio[i]);
}
static void knapsack(int u,int n,float w[],float p[]){
float x[]=new float[10],tp=0;
int i;
for(i=1; i<=n; i++)
x[i]=0;
for(i=1; i<=n; i++){
if(w[i]>u)
break;
else{
x[i]=1;
tp=tp+p[i];
u=(int) (u-w[i]);
}
}
if(i<n)
x[i]=u/w[i];
tp=tp+(x[i]*p[i]);
[Link]("\nThe result is = ");
for(i=1; i<=n; i++)
[Link]("\t"+x[i]);
[Link]("\nMaximum profit is = "+tp);
}
}

5) To find shortest paths to other vertices from a given vertex in a weighted

connected graph, using Dijkstra's algorithm.

package lab7;

import [Link];

public class dijkstra {

int d[]=new int[10];

int p[]=new int[10];
int visited[]=new int[10];

public void dijk(int[][]a, int s, int n)

{
int u=-1,v,i,j,min;
for(v=1;v<=n;v++)
{
d[v]=999;
p[v]=-1;
}

d[s]=0;

for(i=1;i<=n;i++) //perform relaxation operation n times

{
min=999;
for(j=1;j<=n;j++)
{
if(d[j]<min && visited[j]==0) //select a vertex with minimum weight take that as u
{ // and also make that vertex as visited vertex
min=d[j];
u=j;
}
}
visited[u]=1;

for(v=1;v<=n;v++)
{
if((d[u]+a[u][v]<d[v]) && (u!=v) && visited[v]==0)
{
d[v]=d[u]+a[u][v]; //from the visited vertex u, relax the other vertices
p[v]=u; //and for the relaxed vertices v, make the parent vertex as u
}
}
}
 }

void path(int v, int s)

{
if(p[v]!=-1)
path(p[v],s);
[Link]("->"+v+" ");
}
void display(int s, int n)
{
int i;
for(i=1; i<=n; i++)
{
path(i,s);
[Link]("="+d[i]+" ");
[Link]();
}
}

public static void main(String[] args) {

int a[][]=new int[10][10];
int i,j,n,s;
[Link]("Enter the number of vertices");
Scanner sc= new Scanner([Link]);
n=[Link]();

[Link]("Enter the Weighted matrix");

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=[Link]();

[Link]("Enter the source vertex");

s=[Link]();

dijkstra dj = new dijkstra();

[Link](a,s,n);

[Link]("The shortest path between source "+s+ " to remaining vertices are");
[Link](s,n);

[Link]();
}
}

6) To find Minimum Cost Spanning Tree of a given connected undirected graph

using Kruskal's algorithm. Use Union-Find algorithms in your program.

package lab8;

import [Link];
public class kruskal {

int parent[] = new int[10];

int find(int m)
{
int p=m;
while(parent[p]!=0)
p=parent[p];
return p;
}
void union(int i, int j)
{
if(i<j)
parent[i]=j;
else
parent[j]=i;
}

void kruskals(int[][]a, int n)

{
int u=0,v=0,min,k=0,i,j,sum=0;

while(k<n-1)
{
min=999;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(a[i][j]<min && i!=j)
{
min=a[i][j];
u=i;
v=j;
}

i=find(u);
j=find(v);

if(i!=j)
{
union(i,j);
[Link]("("+u+","+v+")"+"="+a[u][v]);
sum=sum+a[u][v];
k++;
}
a[u][v]=a[v][u]=999;
}
[Link]("The cost of minimum spanning tree = "+sum);
}

public static void main(String[] args) {

// TODO Auto-generated method stub
Scanner sc = new Scanner([Link]);
int a[][]=new int[10][10];
int i,j,n;

[Link]("Enter the number of vertices");

 n=[Link]();

[Link]("Enter the weighted matrix");

for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
a[i][j] = [Link]();

[Link]("Entered weighted matrix");

for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
[Link](a[i][j]+"\t");

[Link]("");
}
kruskal k = new kruskal();
[Link](a,n);

[Link]();
}

7) To find Minimum Cost Spanning Tree of a given connected undirected

graph using Prim's algorithm.

package lab9;

import [Link];

public class prims {

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

int weight[][]=new int[10][10];
int n,i,j,source,vertex=0;
int min, sum=0,u=0,v=0;
int visited[]=new int [10];

[Link]("Enter the number of vertices");

n=[Link]();

for(i=1; i<=n; i++)

visited[i]=0;

[Link]("Enter the weighted graph/ cost matrix");

for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
weight[i][j] = [Link]();
 [Link]("Enter the source vertex");
source=[Link]();

visited[source]=1; //Visited

vertex=1;

while(vertex<=n-1)
{
min=999;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(visited[i]==1 && visited[j]==0)
if(i!=j && min>weight[i][j])
{
min=weight[i][j]; //Minimum cost
u=i; //Source
v=j; //Destination

}
visited[v]=1; //visited
sum=sum+min;
vertex++;
[Link](u+"-->"+v+"="+min);
}

[Link]("The cost of minimum spanning tree is "+sum);

[Link]();
}
}

8) Solve All-Pairs Shortest Paths problem using Floyd's algorithm.

package lab10a;

import [Link];

public class floyds {

public static void main(String[] args) {

int a[][]=new int[10][10];
int i, j;
Scanner in = new Scanner([Link]);

[Link]("***********FLOYD'SALGORITHM**********");
[Link]("Enter the number of vertices: ");
int n = [Link]();

[Link]("Enter the adjacency matrix");

 for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j] = [Link]();

[Link]("Entered adjacency matrix is: ");

for(i=1;i<=n;i++)
{
for(j=1; j<=n; j++)
{
[Link](a[i][j]+"\t");
}
[Link]();
}

floyd(a,n);

[Link]("All pair shortest path matrix:");

for (i=1; i<=n; i++)
{
for (j=1; j<=n; j++)
[Link](a[i][j]+"\t");
[Link]();
}

}
static void floyd(int a[][],int n)
{
for (int k=1; k<=n; k++)
{
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
a[i][j] = [Link](a[i][j], a[i][k] + a[k][j]);
}
}

9) Solve Travelling Sales Person problem using Dynamic programming.

package lab10b;

import [Link];

public class lab10b {

static int tspdp(int c[][], int tour[], int start, int n)

{
int mintour[]=new int[10], temp[]=new int[10], mincost=999, ccost, i, j, k;

if(start == n-1)
return (c[tour[n-1]][tour[n]] + c[tour[n]][1]); //final cost

for(i=start+1; i<=n; i++) {

for(j=1; j<=n; j++)
 temp[j] = tour[j];
temp[start+1] = tour[i];
temp[i] = tour[start+1];

if((c[tour[start]][tour[i]]+(ccost=tspdp(c,temp,start+1,n)))<mincost) {
mincost = c[tour[start]][tour[i]] + ccost;
for(k=1; k<=n; k++)
mintour[k] = temp[k];
}
}

for(i=1; i<=n; i++)

tour[i] = mintour[i];
return mincost;
}

public static void main(String[] args) {

int c[][]=new int[10][10], tour[]=new int[10];

Scanner in = new Scanner([Link]);
int i, j,cost;

[Link]("**** TSP DYNAMIC PROGRAMMING *******");

[Link]("Enter the number of cities: ");

int n = [Link]();

if(n==1)
{
[Link]("Path is not possible");
[Link](0);
}

[Link]("Enter the cost matrix");

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
c[i][j] = [Link]();

[Link]("The entered cost matrix is");

for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
[Link](c[i][j]+"\t");
}
[Link]();
}

for(i=1;i<=n;i++)
tour[i]=i; //tour of every node is itself in the beginning

cost = tspdp(c, tour, 1, n);

[Link]("The optimal tour is ");

for(i=1;i<=n;i++)
[Link](tour[i]+"->");
[Link]("1");
[Link]("The accurate mincost is "+cost);
 [Link]("******* ************* ***************");

}
}
10) Solve 0/1 Knapsack problem using Dynamic Programming method.
/* A Naive recursive implementation of 0-1 Knapsack problem */
class Knapsack {

// A utility function that returns maximum of two integers

s static int max(int a, int b) { return (a > b) ? a : b; }

// Returns the maximum value that can

// be put in a knapsack of capacity W
static int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;

// If weight of the nth item is more

// than Knapsack capacity W, then
// this item cannot be included in the optimal solution
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);

// Return the maximum of two cases:

// (1) nth item included
// (2) not included
else
return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}

// Driver program to test above function

public static void main(String args[])
{
int val[] = new int[] { 60, 100, 120 };
int wt[] = new int[] { 10, 20, 30 };
int W = 50;
int n = [Link];
[Link](knapSack(W, wt, val, n));
}
}

11) Design and implement C++/Java Program to find a subset of a given set S =
{Sl, S2,…, Sn} of n positive integers whose SUM is equal to a given positive
integer d. 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.

package lab11;

import [Link];

public class subset {

 static int c=0;
public static void main(String[] args) {
int w[]=new int[10];
int n, d, i, sum=0;
int x[]=new int[10];
Scanner in=new Scanner([Link]);

[Link]("********** SUBSET PROBLEM ************");

[Link]("Enter the number of elements: ");
n=[Link]();

[Link]("Enter the elements in increasing order");

for(i=0;i<n;i++)
w[i]=[Link]();
[Link]("Enter the value of d: ");
d=[Link]();

for(i=0;i<n;i++)
sum=sum+w[i];

[Link]("SUM ="+sum);

if(sum < d || w[0] > d)

{
[Link]("Subset is not possible ! ");
[Link]("********** *********** *************");
[Link](0);
}

subsetproblem(0,0,sum,x,w,d);

if(c==0)
[Link]("Subset is not possible ! ");
[Link]("\n********** ********* *************");
}

static void subsetproblem(int cs, int k, int r,int x[],int w[],int d)

{
x[k] = 1;
if(cs+w[k] == d)
{
c++;
[Link]("\nSolution "+c+" is {");
for(int i=0;i<=k;i++)
if(x[i] == 1)
{
[Link](w[i]+" ");
}
[Link]("}");
}
else if((cs + w[k] + w[k+1]) <= d)
subsetproblem(cs + w[k], k+1, r-w[k],x,w,d);

if((cs + r - w[k]) >= d && (cs + w[k+1]) <= d)

{
x[k] = 0;
subsetproblem(cs, k+1, r-w[k],x,w,d);
 }
}
}

12) Design and implement C++/Java Program to find all Hamiltonian Cycles in
a connected undirected Graph G of n vertices using backtracking principle.

import [Link];
public class hamiltonial
{
static int n;
public static void main(String[] args)
{
Scanner in=new Scanner([Link]);
[Link]("Enter the number of vertices:");
n=[Link]();
int graph[][]=new int[10][10];
[Link]("Enter the adjacency matrix:");
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
graph[i][j]=[Link]();
[Link]("Entered matrix is:");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
[Link](graph[i][j]+"\t");
[Link]();
}
hamcycle(graph);
[Link]("***************************");
}

static void printsol(int path[])

{
[Link]("Solution exists");
[Link]("following is one cycle");
for(int i=0;i<n;i++)
[Link](path[i]+" ");
[Link](path[0]);
}

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

static boolean hamcycleutil(int graph[][],int path[],int pos)

{
if(pos==n)
{
if(graph[path[pos-1]][path[0]]==1)
return true;
 else
return false;
}
for(int v=1;v<n;v++)
{
if(issafe(v,graph,path,pos))
{
path[pos]=v;
if(hamcycleutil(graph,path,pos+1) == true)
return true;
path[pos]=-1;
}
}
return false;
}

static boolean hamcycle(int graph[][])

{
int path[]=new int[n+1];
for(int i=0;i<n;i++)
path[i]=-1;
path[0]=0;
if(hamcycleutil(graph,path,1) == false)
{
[Link]("Solution does not exist");
return false;
}
printsol(path);
return true;
}
}