DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

SRI SAIRAM COLLEGE OF ENGINEERING, BENGALURU

DEPARTMENT OF COMPUTER SCIENCE AND

ENGINEERING

IV SEMESTER

21CS42 - DESIGN AND ANALYSIS OF

ALGORITHMS LABORATORY

LABORATORY MANUAL

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

Programs List:
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.

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.

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.

4. Write & Execute C++/Java Program To solve Knapsack problem using Greedy method
5. 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.

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

7. Write & Execute C++/Java Program To find Minimum Cost Spanning Tree of a given connected undirected
graph using Prim's algorithm.

8. Write C++/ Java programs to Solve All-Pairs Shortest Paths problem using Floyd's algorithm.
9. Write C++/ Java programs to Solve Travelling Sales Person problem using Dynamic programming.
10. Write C++/ Java programs to Solve 0/1 Knapsack problem using Dynamic Programming method.
11. Design and implement C++/Java Program to find a subset of a given set S = {Sl, S2,…, Sn} of npositive
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.

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

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

Vision of the Department
Transform students into professional, ethical engineers to meet global challenges through
quality education.

Mission of the Department

M1. To impart quality education in Computer Science and Engineering with the strong
industry institute partnership to develop technical & research skills.
M2. Enrich the technical ability of students to face the world with confidence,
commitment and team-work in IT field.

M3. Provide a learning platform for interdisciplinary innovation, research and Self-
learning.
M4. Encourage faculty and students to actively participate in holistic educational
practices and to impart social values.
Program Educational Objectives (PEOs)
Graduates develop knowledge in the core areas of Computer Science Engineering and
PEO 1 enhance technical and research skills for providing software solutions

Graduates will pursue technical and managerial skills to analyze and develop problem
PEO 2 solving abilities of Computer Science and Engineering through Mathematics, Science
and Engineering to encounter industrial needs.
Graduates develop effective communication and management skills to interact
PEO 3 effectively with stakeholders in the field of Computer Science Engineering and develop
innovative solutions for real time problems.
Graduates with Lifelong learning demonstrate skills and knowledge in the domain of
PEO 4 computer programming and exhibit leadership qualities, team work, social and ethical
values.

Program Specific Outcomes (PSOs):

The ability to understand, analyze and develop computer programs in the areas
PSO-1 related to algorithms, system software, networking and embedded computing, web
design, and data analytics for efficient design of computer-based systems.
The ability to understand the evolutionary changes in computing technologies, apply
standard practices and strategies in software project development and testing using
PSO-2
various programming environments to deliver a quality product for business, real
world problems and meet the challenges of the future.

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

PROGRAM OUTCOMES (POs)

Engineering knowledge: Apply the knowledge of mathematics, science, engineering fundamentals,
PO1
and an engineering specialization to the solution of complex engineering problems.

Problem analysis: Identify, formulate, review research literature, and analyze complex engineering
PO2 problems reaching substantiated conclusions using first principles of mathematics, natural sciences,
and engineering sciences.

Design/development of solutions: Design solutions for complex engineering problems and design
PO3 system components or processes that meet the specified needs with appropriate consideration for the
public health and safety, and the cultural, societal, and environmental considerations.

Conduct investigations of complex problems: Use research-based knowledge and research methods
PO4 including design of experiments, analysis and interpretation of data, and synthesis of the information to
provide valid conclusions
Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern
PO5 engineering and IT tools including prediction and modeling to complex engineering activities with an
understanding of the limitations.
The engineer and society: Apply reasoning informed by the contextual knowledge to assess societal,
PO6 health, safety, legal and cultural issues and the consequent responsibilities relevant to the professional
engineering practice.
Environment and sustainability: Understand the impact of the professional engineering solutions in
PO7 societal and environmental contexts, and demonstrate the knowledge of, and need for sustainable
development.
Ethics: Apply ethical principles and commit to professional ethics and responsibilities and norms of the
PO8
engineering practice.

Individual and team work: Function effectively as an individual, and as a member or leader in diverse
PO9
teams, and in multidisciplinary settings.

Communication: Communicate effectively on complex engineering activities with the engineering

PO10 community and with society at large, such as, being able to comprehend and write effective reports and
design documentation, make effective presentations, and give and receive clear instructions.
Project management and finance: Demonstrate knowledge and understanding of the engineering and
PO11 management principles and apply these to one’s own work, as a member and leader in a team, to manage
projects and in multidisciplinary environments.
Life-long learning: Recognize the need for, and have the preparation and ability to engage in
PO12
independent and life-long learning in the broadest context of technological change.

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

Course outcomes:

CO Statement
No.
C42.1 Analyze the performance of the algorithms, state the efficiency using asymptotic
notations and analyze mathematically the complexity of the algorithm.

C42.2 Apply divide and conquer approaches and decrease and conquer approaches in solving
the problems analyze the same

C42.3 Apply the appropriate algorithmic design technique like greedy method, transform and
conquer approaches and compare the efficiency of algorithms to solve the given
problem.

C42.4 Apply and analyze dynamic programming approaches to solve some problems. and
improve an algorithm time efficiency by sacrificing space.

C42.5 Apply and analyze backtracking, branch and bound methods and to describe P, NP and
NP-Complete problems.

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 java.util.Scanner;
import java.util.Random;
import java.io.*;

public class SelectionSort

{
public static void main(String[] args) throws FileNotFoundException
{
Scanner scan=new Scanner (System.in);
PrintStream o = new PrintStream(new File("A.txt"));
PrintStream console=System.out;
System.out.println("Enter the no. of elements to be sorted :");
int n=scan.nextInt();
int a[]=new int[n+1];
long start,end;
Random rand=new Random();
for(int i=0;i<n;i++)
{
a[i]=rand.nextInt(n);

}
System.out.println("Array elements to be sorted are :");
System.out.println("Please refer to the file");

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

System.setOut(o);
for(int i=0;i<n;i++)
{
System.out.println(a[i]+" ");
}
a[n]=99999;
start=System.nanoTime();
ssort(a,n);
end=System.nanoTime();
System.out.println("\nThe sorted elements are :");
for(int i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
System.setOut(console);
long estimatedTime=end-start;
System.out.println("\nSelection Sort in Average case is:
"+(estimatedTime/1000000000.0)+"s");
System.out.println("******************************************");
start= System.nanoTime();
ssort(a,n);
end=System.nanoTime();
estimatedTime=end-start;
System.out.println("\nSelection Sort in best case is: "+
(estimatedTime/1000000000.0)+"s");
System.out.println("******************************************");

generateworstcase(a,n);
start= System.nanoTime();
ssort(a,n);
end=System.nanoTime();
estimatedTime=end-start;
System.out.println("\nSelection Sort in worst case is: "+
(estimatedTime/1000000000.0)+"s");
System.out.println("******************************************");
}
static void generateworstcase(int a[],int n)
{
for (int i = 0; i < n-1; i++)
{
int max_element = i;
for (int j = i+1; j < n; j++)
if (a[j] > a[max_element])
max_element = j;
if(max_element!=i)
{
int temp = a[max_element];//swap the elements
a[max_element] = a[i];
a[i] = temp;
}
}
}
static void ssort(int array[],int n)
{
for (int i = 0; i < n-1; i++)
{

int min_element = i;
for (int j = i+1; j < n; j++)

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

if (array[j] < array[min_element])

min_element = j;
if(min_element!=i)
{
int temp = array[min_element];//swap the elements
array[min_element] = array[i];
array[i] = temp;
}
}

}
}

OUTPUT:

Enter the no. of elements to be sorted :

5000
Array elements to be sorted are :
Please refer to the file

Selection Sort in Average case is:0.0211881s

******************************************

Selection Sort in best case is: 0.0154307s

******************************************

Selection Sort in worst case is:0.0319938s

******************************************

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

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 java.util.Scanner;
import java.util.Random;
import java.io.*;

public class QuickSort

{
public static void main(String[] args) throws FileNotFoundException
{
Scanner scan=new Scanner (System.in);
PrintStream o = new PrintStream(new File("A.txt"));
PrintStream console=System.out;
System.out.println("Enter the no. of elements to be sorted :");
int n=scan.nextInt();
int a[]=new int[n+1];
long start,end;
Random rand=new Random();
for(int i=0;i<n;i++)
{
a[i]=rand.nextInt(n);
}
System.out.println("Array elements to be sorted are :");
System.out.println("Please refer to the file");
System.setOut(o);
for(int i=0;i<n;i++)
{
System.out.println(a[i]+" ");
}
a[n]=99999;
start=System.nanoTime();
qsort(a,0,n-1);
end=System.nanoTime();
System.out.println("\nThe sorted elements are :");
for(int i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
System.setOut(console);
long estimatedTime=end-start; System.out.println("\nQuick Sort in
Average case is: "+(estimatedTime/1000000000.0)+"s");
System.out.println("******************************************");
start= System.nanoTime();
qsort(a,0,n-1);
end=System.nanoTime();
estimatedTime=end-start;
System.out.println("\nQuick Sort in Worst case is:
"+(estimatedTime/1000000000.0)+"s");

System.out.println("******************************************");
bestcasegen(a,0,n-1);
start=System.nanoTime();
qsort(a,0,n-1);
Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru
DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

end=System.nanoTime();
estimatedTime=end-start;
System.out.println("\nQuickSort in BestCase is:
"+(estimatedTime/1000000000.0)+"s");
System.out.println("******************************************");
}

static void bestcasegen(int[] arr, int begin, int end)

{
int count = end-begin+1;
if(count <= 2)
return;
int middle = (begin + end) / 2;
bestcasegen(arr, begin, middle);
swap(arr, begin, middle);
bestcasegen(arr, ++middle, end);
}
static void swap(int[] arr, int i, int j)
{
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

static void qsort(int a[],int p,int q)

{
int j;
if(p<q)
{
j=partition(a,p,q);
qsort(a,p,j-1);
qsort(a,j+1,q);
}
}

static int partition(int a[],int m,int p)

{
int v,i,j;
v=a[m];
i=m;
j=p;
while(i<=j)
{
while(a[i]<=v) i++;
while(a[j]>v) j--;
if(i<j)
interchange(a,i,j);
}
a[m]=a[j];
a[j]=v;
return j;
}
static void interchange(int a[],int i,int j)
{
int p;
p=a[i];
a[i]=a[j];
a[j]=p;
}
}

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

OUTPUT:

Enter the no. of elements to be sorted :

5000
Array elements to be sorted are :
Please refer to the file

Quick Sort in Average case is: 0.001687712s

******************************************

Quick Sort in Worst case is: 0.012835776s

******************************************

QuickSort in BestCase is: 2.5663E-4s

******************************************

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

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 tosort. Plot a graph of the time
taken versus non graph sheet. The elements can be read from a file orcan 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 java.io.*;
import java.util.Random;
import java.util.Scanner;

public class Mergesort

{
int n;
int a[];
Mergesort()
{
System.out.println("Enter the array size");
Scanner sc =new Scanner(System.in);
n=sc.nextInt();
a= new int[n];
Random rand=new Random();
for(int i=0;i<n;i++)
a[i]=rand.nextInt(20);

try{
calc();
}
catch(FileNotFoundException e)
{
System.out.println(e);
}
}
void calc() throws FileNotFoundException
{
PrintStream o = new PrintStream(new File("A.txt"));
PrintStream console=System.out;
System.out.println();
mergesort(a,0,n-1);
System.out.println("Array elements to be sorted are :");
System.out.println("Please refer to the file");
System.setOut(o);
for(int i=0;i<n;i++)
{
System.out.println(a[i]+" ");
}
long startTime=System.nanoTime();
mergesort(a,0,n-1);
long stopTime=System.nanoTime();
long elapseTime=(stopTime-startTime);
System.out.println("\nThe sorted elements are :");
for(int i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
System.setOut(console);

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

long estimatedTime=stopTime-startTime;
System.out.println("\nMerge sort in average case is:
"+(estimatedTime/1000000000.0)+" s");

System.out.println("******************************************");

startTime=System.nanoTime();
mergesort(a,0,n-1);
stopTime=System.nanoTime();
estimatedTime=stopTime-startTime;
System.out.println("\nMerge sort in Best case is:
"+(estimatedTime/1000000000.0)+" s");

System.out.println("******************************************");

generateWorstCase(a,0,n-1);
startTime=System.nanoTime();
mergesort(a,0,n-1);
stopTime=System.nanoTime();
estimatedTime=stopTime-startTime;
System.out.println("\nMerge sort in Worst case is:
"+(estimatedTime/1000000000.0)+" s");

System.out.println("******************************************");

}
void generateWorstCase(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
int[] left = new int[m - l + 1];
int[] right = new int[r - m];
split(arr, left, right, l, m, r);
generateWorstCase(left, l, m);
generateWorstCase(right, m + 1, r);
join(arr, left, right, l, m, r);
}
}

static void join(int arr[], int left[], int right[], int l, int m,
int r)
{
int i;
for (i = 0; i <= m - l; i++)
arr[i] = left[i];
for (int j = 0; j < r - m; j++)
arr[i + j] = right[j];
}

static void split(int arr[], int left[], int right[], int l, int m,
int r)
{
for (int i = 0; i <= m - l; i++)
left[i] = arr[i * 2];

for (int i = 0; i < r - m; i++)

right[i] = arr[i * 2 + 1];

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

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

{
if(low<high)
{
int mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(low,mid,high);
}
}

void merge(int low, int mid,int high)

{
int i=low;
int j=mid+1;
int k=low;
int[]resarray;
resarray=new int[n];
while(i<=mid&&j<=high)
{
if(a[i]<a[j])
{
resarray[k]=a[i];
i++;
k++;
}
else
{
resarray[k]=a[j];
j++;
k++;
}
}

while(i<=mid)
resarray[k++]=a[i++];
while(j<=high)
resarray[k++]=a[j++];
for(int m=low;m<=high;m++)
a[m]=resarray[m];
}

public static void main(String[] args)

{
new Mergesort();
}
}

OUTPUT:
Enter the array size
5000

Array elements to be sorted are :

Please refer to the file

Merge sort in average case is: 0.050339267 s

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

******************************************

Merge sort in Best case is: 0.051175797 s

******************************************

Merge sort in Worst case is: 0.05285831 s

******************************************

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

4 Write & Execute C++/Java Program To solve Knapsack problem using Greedy method

import java.util.Scanner;
public class FractionalKnapSack
{
double weight[];
double profit[];
double ratio[];
double m;
double sum;
FractionalKnapSack()
{
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of objects: ");
int n= scan.nextInt();
weight = new double[n];
profit = new double[n];
ratio = new double[n];
System.out.println("Enter the object's weights");
for (int i = 0; i<n; ++i)
weight[i] = scan.nextDouble();
System.out.println("Enter the object's profits");
for (int i = 0; i<n; ++i)
profit[i] = scan.nextDouble();
for (int i = 0; i<n; ++i)
ratio[i] = profit[i] / weight[i];
System.out.println("Enter the Capacity of the knapsack: ");
m = scan.nextDouble();
scan.close();
}

int getNext()
{
double highest = 0;
int index = -1;
for (int i = 0; i<profit.length; ++i)
{
if (ratio[i] >highest)
{
highest = ratio[i];
index = i;
}
}
return index;
}
void fill()
{
System.out.print("Objects considered: ");
while(m>0)
{
int item = getNext();
if (item == -1) break;
System.out.print((item+1)+" ");
if(weight[item]<= m)
{

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

m=m-weight[item];
sum=sum+profit[item];
ratio[item]=0;
}

else
{
sum=sum+(profit[item]*(m/weight[item]));
m=0;
break;
}
}
System.out.println("\nThe Optimal Solution i.e.Maximum Profit =" + sum );
}
public static void main(String[] args)
{
FractionalKnapSack fk = new FractionalKnapSack();
fk.fill();
}
}

OUTPUT:

Enter the number of objects:

3
Enter the object's weights
20 25 10
Enter the object's profits
30 40 35
Enter the Capacity of the knapsack:
40
Objects considered: 3 2 1
The Optimal Solution i.e.Maximum Profit = 82.5

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

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

import java.util.Scanner;
public class Dijkstra
{
int graph[][]=new int[10][10];
int d[]=new int[10];
int p[]=new int[10];
int s[]=new int[10];
int n;
int source;
int min;
Dijkstra()
{
Scanner scan=new Scanner(System.in);
System.out.println("Enter the number of vertices");
n=scan.nextInt();
System.out.println("Enter the adjacency matrix");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
graph[i][j]=scan.nextInt();
}
}
System.out.println("Enter the source vertex");
source=scan.nextInt();
}
void initialize()
{
for(int i=0;i<n;i++)
{
d[i]=graph[source][i];
p[i]=source;
}
s[source]=1;
}
void dijkstra()
{
relax(source);
for(int i=0;i<n;i++)
{
if(d[i]==99)
System.out.println(i+ "is not reachable from" +
source);
if(i!=source)
print_path(source,i);
}
}

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

void print_path(int source,int dest)

{
int i;
i=dest;
while(i!=source)
{
System.out.print(i+"<--");
i=p[i];
}
System.out.print(i+"="+d[dest]);
System.out.println();
}

void relax(int source)

{
for(int i=1;i<n;i++)
{
min=99;
int u=-1;
for(int j=0;j<n;j++)
{
if(s[j]==0)
{
if(d[j]<min)
{
min=d[j];
u=j;
}
}
}
if(u==-1) return;
s[u]=1;
for(int v=0;v<n;v++)
{
if(s[v]==0 && d[v]>d[u]+graph[u][v])
{
d[v]=d[u]+graph[u][v];
p[v]=u;
}
}
}
}
public static void main(String[] args)
{
Dijkstra d=new Dijkstra();
d.initialize();
d.dijkstra();
}
}

OUTPUT:

Enter the number of vertices

5

Enter the adjacency matrix

0 3 99 7 99
3 0 4 2 99
99 4 0 5 6

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

5 2 5 0 4
99 99 6 4 0

Enter the source vertex

0

1<--0=3
2<--1<--0=7
3<--1<--0=5
4<--3<--1<--0=9

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

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

import java.util.Scanner;
public class Kruskal
{
int cost[][]=new int[10][10];
int s[]=new int[10];
int t[][]=new int[10][10];
int n,sum,k,u,v,count;

Kruskal()
{
Scanner scan=new Scanner(System.in);
System.out.println("Enter the number of vertices");
n=scan.nextInt();
System.out.println("Enter the adjacency matrix");
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cost[i][j]=scan.nextInt();
for(int i=0;i<n;i++)
{
s[i]=i;
}
}

int findParent(int v)
{
while(s[v]!=v)
{
v=s[v];
}
return v;
}

void kruskal()
{
int i,j;
while(count<n-1)
{
int min=99;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(min>cost[i][j])
{
min=cost[i][j];
u=i;
v=j;
}
}
}
k++;
}

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42
}
if(min==99) break;
i=findParent(u);
j=findParent(v);
if(i!=j)
{ t[k][0]=
u;
t[k][1]=v;
sum=sum+min;
count++;
s[v]=u;
}
cost[u][v]=cost[v][u]=99;
printTree();
}

void printTree()
{
if(count==n-1)
{
System.out.println("Cost of Spanning tree is: "+sum);
System.out.println("The spanning tree is:");
for(k=0;k<n-1;k++)
{
System.out.println(t[k][0]+ " - "+t[k][1]);
}
System.exit(0);
}
}

public static void main(String[] args)

{Kruskal k=new Kruskal();
k.kruskal();

}
}

OUTPUT:

Enter the number of vertices

6

Enter the adjacency matrix

0 3 99 99 6 5
3 0 1 99 99 4
99 1 0 6 99 4
99 99 6 0 8 5
6 99 99 8 0 2
5 4 4 5 2 0

Cost of Spanning tree is: 15

The spanning tree is:
1 - 2
4 - 5
0 - 1
1 - 5
3 - 5

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

7 Write & Execute C++/Java Program To find Minimum Cost Spanning Tree of a given connected undirected
graph using Prim's algorithm.
import java.util.Scanner;
public class Prims
{
int n;
int graph[][]=new int[10][10];
int p[]=new int[10];
int d[]=new int[10];
int s[]=new int[10];
int t[][]=new int[10][2];
int sum,k,source,u,v;

void createGraph()
{
Scanner scan =new Scanner(System.in);
System.out.println("Enter the number of vertices");
n=scan.nextInt();
System.out.println("Enter the adjacency matrix");
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
graph[i][j]=scan.nextInt();
}
System.out.println("Enter an arbitrary vertex");
source=scan.nextInt();
scan.close();
}

void initialize()
{
for(int i=0;i<n;i++)
{
d[i]=graph[source][i];
p[i]=source;
}
s[source]=1;
}

void MST()
{
for(int i=1;i<n;i++)
{
int min=99;
for(int 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++;

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42
sum+=graph[u][p[u]];
s[u]=1;

for(v=0;v<n;v++)
{
if(s[v]==0 && graph[u][v]<d[v])
{
d[v]=graph[u][v];
p[v]=u;
}
}
}
}
void print()
{
if(sum>=99)
System.out.println("Spanning tree does not exist");
else
{
for(int i=0;i<n-1;i++)
{
System.out.println(t[i][0]+"->"+t[i][1]);
}
System.out.println("The cost of spanning tree is: "+sum);
}
}

public static void main(String[] args)

{
Prims p=new Prims();
p.createGraph();
p.initialize();
p.MST();
p.print();
}
}

OUTPUT:

Enter the number of vertices

6
Enter the adjacency matrix
0 3 99 99 6 5
3 0 1 99 99 4
99 1 0 6 99 4
99 99 6 0 8 5
6 99 99 8 0 2
5 4 4 5 2 0
Enter an arbitrary vertex
1
2->1
0->1
5->1
4->5
3->5
The cost of spanning tree is: 15

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

8 Write C++/ Java programs to Solve All-Pairs Shortest Paths problem using Floyd's algorithm.
import java.util.Scanner;
public class Floyds
{
int cost[][];
int n;
Floyds()
{
Scanner scan=new Scanner(System.in);
System.out.println("Enter the number of vertices");
n=scan.nextInt();
cost=new int[n+1][n+1];
System.out.println("Enter the cost matrix");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cost[i][j]=scan.nextInt();
}
}
}

void floyds()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cost[i][j]=Math.min(cost[i][j],
cost[i][k]+cost[k][j]);
printAllPairShortestPath();
}

void printAllPairShortestPath()
{
System.out.println("The shortest path matrix is");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
System.out.print(cost[i][j]+" ");
}
System.out.println();
}
}

public static void main(String[] args)

{Floyds f=new Floyds();
f.floyds();

OUTPUT:
Enter the number of vertices
4
Enter the cost matrix

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42
0 99 3 99
2 0 99 99
99 7 0 1
6 99 99 0

The shortest path matrix is

0 10 3 4
2 0 5 6
7 7 0 1
6 16 9 0

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

9 Write C++/ Java programs to Solve Travelling Sales Person problem using Dynamic programming

import java.util.*;
public class TSP
{
int weight[][],n,tour[],finalCost;
final int INF=999;

public TSP()
{
Scanner s=new Scanner(System.in);
System.out.println("Enter no. of nodes:=>");
n = s.nextInt();
weight=new int[n][n];
tour=new int[n-1];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i!=j)
{
System.out.print("Enter weight of "+(i+1)+" to
"+(j+1)+":=>");
weight[i][j]=s.nextInt();
}
}
}

System.out.println();
System.out.println("Starting node assumed to be node 1.");
eval();
}

public int COST(int currentNode,int inputSet[],int setSize)

{
if(setSize==0)
return weight[currentNode][0];
int min=INF,minindex=0;
int setToBePassedOnToNextCallOfCOST[] = new int[n-1];
for(int i=0;i<setSize;i++)
{
int k=0;
for(int j=0;j<setSize;j++)
{
if(inputSet[i]!=inputSet[j])
setToBePassedOnToNextCallOfCOST[k++]=inputSet[j];
}

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

int temp=COST(inputSet[i],setToBePassedOnToNextCallOfCOST,setSize-1);
if((weight[currentNode][inputSet[i]]+temp) < min)
{
min=weight[currentNode][inputSet[i]]+temp;
minindex=inputSet[i];
}
}
return min;
}

public int MIN(int currentNode,int inputSet[],int setSize)

{
if(setSize==0)
return weight[currentNode][0];
int min=INF,minindex=0;
int setToBePassedOnToNextCallOfCOST[]=new int[n-1];for(int
i=0;i<setSize;i++)
{
int k=0;
for(int j=0;j<setSize;j++)
{
if(inputSet[i]!=inputSet[j])

setToBePassedOnToNextCallOfCOST[k++]=inputSet[j];
}
int
temp=COST(inputSet[i],setToBePassedOnToNextCallOfCOST,setSize-1);
if((weight[currentNode][inputSet[i]]+temp) < min)
{
min=weight[currentNode][inputSet[i]]+temp;
minindex=inputSet[i];
}
}
return minindex;
}

public void eval()

{
int dummySet[]=new int[n-1];
for(int i=1;i<n;i++)
dummySet[i-1]=i;
finalCost = COST(0,dummySet,n-1);
constructTour();
}

public void constructTour()

{
int previousSet[]=new int[n-1];
int nextSet[]=new int[n-2];
for(int i=1;i<n;i++)
previousSet[i-1]=i;
int setSize=n-1;
tour[0]=MIN(0,previousSet,setSize);
for(int i=1;i<n-1;i++)
{
int k=0;
for(int j=0;j<setSize;j++)
{
}
--setSize;

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

if(tour[i-1]!=previousSet[j])
nextSet[k++]=previousSet[j];
tour[i]=MIN(tour[i-1],nextSet,setSize);
for(int j=0;j<setSize;j++)
previousSet[j]=nextSet[j];
}
display();
}

public void display()

{
System.out.println();
System.out.print("The tour is 1-");
for(int i=0;i<n-1;i++)
System.out.print((tour[i]+1)+"-");
System.out.print("1");
System.out.println();
System.out.println("The final cost is "+finalCost);
}

public static void main(String args[])

{
TSP obj=new TSP();
}
}

OUTPUT:

Enter no. of nodes:=>

4
Enter weight of 1 to 2:=>2
Enter weight of 1 to 3:=>5
Enter weight of 1 to 4:=>7
Enter weight of 2 to 1:=>2
Enter weight of 2 to 3:=>8
Enter weight of 2 to 4:=>3
Enter weight of 3 to 1:=>5
Enter weight of 3 to 2:=>8
Enter weight of 3 to 4:=>1
Enter weight of 4 to 1:=>7
Enter weight of 4 to 2:=>3
Enter weight of 4 to 3:=>1

Starting node assumed to be node 1.

The tour is 1-2-4-3-1

The final cost is 11
 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

10. Write C++/ Java programs to Solve 0/1 Knapsack problem using Dynamic Programming method.

import java.util.Scanner;
public class Knapsack
{
static int max(int a,int b)
{
return (a>b)?a:b;
}

static void knapsack(int wt[],int profit[],int m,int n)

{
int x[]=new int[n+1];
int i,j;
int V[][]=new int[n+1][m+1];
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(i==0 || j==0) V[i][j]=0;
else if(wt[i]<=j) V[i][j]=max(profit[i]+V[i-1][j-
wt[i]],V[i-1][j]);
else V[i][j]=V[i-1][j];
}
}

System.out.println("The optimal solution is: " +V[n][m]);

i=n;
j=m;
while(i!=0 && j!=0)
{
if(V[i][j]!=V[i-1][j])
{
x[i]=1;
j=j-wt[i];
}
i=i-1;
}
System.out.println("The objects selected are:");
for(int z=1;z<=n;z++)
{
if(x[z]==1)
System.out.println(z);
}
}
public static void main(String[] args)
{
Scanner scan= new Scanner(System.in);
System.out.println("Enter the number of objects");
int n=scan.nextInt();
int wt[]=new int[n+1];
int profit[]=new int[n+1];
System.out.println("Enter the weight");
for(int i=1;i<=n;i++)
wt[i]=scan.nextInt();
System.out.println("Enter the profit");

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

for(int i=1;i<=n;i++)
profit[i]=scan.nextInt();
System.out.println("Enter the capacity");
int m=scan.nextInt();
knapsack(wt,profit,m,n);
}
}
OUTPUT:
Enter the number of objects 4
Enter the weight
2 1 3 2
Enter the profit
12 10 20 15
Enter the capacity
5
The optimal solution is: 37
The objects selected are:
1
2
4

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

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.

import java.util.Scanner;

public class Subset

{
int[] w;
int[] x;
int sum;
int total;

public void process()

{
getData();
System.out.println("The subsets are:");
subset(0, 1, total);
}

void getData()
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number of elements:");
int n = sc.nextInt();
w = new int[n + 1];
x = new int[n + 1];
System.out.println("Enter " + n + " Elements :");
for (int i = 1; i <= n ; i++)
{
w[i] = sc.nextInt();
total += w[i];
}
System.out.println("Enter the sum to be obtained: ");
sum = sc.nextInt();
if (total < sum)
{
System.out.println("No possible subsets!!!");
System.exit(1);
}
sc.close();
}
void subset(int s, int k, int r)
{
x[k] = 1;
if (s + w[k] == sum)
{
System.out.print("{");
for (int i = 1; i <= k; i++)
{

if(x[i]==1)
System.out.print(" " + w[i]);
}

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

System.out.println(" }");
}
else if ((s + w[k] + w[k + 1]) <= sum)
{
subset(s + w[k], k + 1, r - w[k]);
}
if ((s + r - w[k]) >= sum && (s + w[k + 1]) <= sum)
{
x[k] = 0;
subset(s, k + 1, r - w[k]);
}
}
public static void main(String[] args)
{

Subset s=new Subset();

s.process();
}
}

OUTPUT:

Enter the number of elements:4

Enter 4 Elements :
7 1 2 3
Enter the sum to be obtained:
10
The subsets are:
{ 7 1 2 }
{ 7 3 }

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42

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 java.util.Scanner;

public class Hamiltonian

{
int adj[][];
int x[];
int n;

Hamiltonian()
{
Scanner scan=new Scanner(System.in);
System.out.println("Enter the number of nodes");
n=scan.nextInt();
x=new int[n+1];
x[1]=1;
for(int i=2;i<=n;i++)
x[i]=0;
adj=new int[n+1][n+1];
System.out.println("Enter the adjacency matrix");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
adj[i][j]=scan.nextInt();
}
}
}

public void nextVertex(int k)

{ int j=0;

while(true)
{
x[k]=(x[k]+1)%(n+1);

if(x[k]==0) return;
if(adj[x[k-1]][x[k]] ==1)
{
for(j=1;j<k;j++)
if(x[j]==x[k]) break;
if(j==k)
{
if((k<n)|| (k==n &&adj[x[n]][1]==1))
return;
}
}
}
}

void H(int k)
{

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru

DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY 21CS42
while(true)
{
nextVertex(k);
if(x[k]==0) return;
if(k==n)
{
System.out.print("solution is: ");
for(int i=1;i<=n;i++)
System.out.print(x[i]+" ");
System.out.println(1);
}
else H(k+1);
}
}

public static void main(String[] args)

{
Hamiltonian c=new Hamiltonian();
c.H(2);
}
}

OUTPUT:

Enter the number of nodes

6
Enter the adjacency matrix
0 1 1 1 0 0
1 0 1 0 0 1
1 1 0 1 1 0
1 0 1 0 1 0
0 0 1 1 0 1
0 1 0 0 1 0
solution is: 1 2 6 5 3 4 1
solution is: 1 2 6 5 4 3 1
solution is: 1 3 2 6 5 4 1
solution is: 1 3 4 5 6 2 1
solution is: 1 4 3 5 6 2 1
solution is: 1 4 5 6 2 3 1

Dept. of CSE Sri Sairam College of Engineering, Anekal, Bengaluru