Angadi Institute of Technology and Management

Design and Analysis of Algorithm Lab
1. a. Create a Java class called Student with the following details as variables within it.
(i) USN
(ii) Name
(iii) Branch
(iv) Phone
Write a Java program to create nStudent objects and print the USN, Name, Branch,
and
Phone of these objects with suitable headings.
b. Write a Java program to implement the Stack using arrays. Write Push(), Pop(), and
Display() methods to demonstrate its working.
PROGRAM:
1a) Student.java
package oneaa;
import java.io.*;
import java.util.Scanner;
class Student
{
long USN;
String Name;
String Branch;
long Phone;
Student (long id,String Nm,String Br,long Ph)
{
USN=id;
Name=Nm;
Branch=Br;
Phone= Ph;
}
void display()
{
System.out.println(USN +"\t"+Name+"\t"+Branch+"\t"+Phone);
}
}
StudentDetails.java
class StudentDetails
{
public static void main(String args[])throws IOException
{
Scanner s1 = new Scanner(System.in);
System.out.println("Enter the number of studens:");

int n= s1.nextInt();
Student[] S= new Student[n];
Dept. Of CSE, AITM Belagavi Page 1

for(int i=0;i<n;i++)
{ System.out.println("Enter the details of Student no:" +(i+1));
System.out.println("Enter the university number:");

long id= s1.nextLong();
System.out.println("Name:");
String Nm= s1.next();
System.out.println("Branch:");
String Br = s1.next();
System.out.println("Phone no:");
long Ph= s1.nextLong();
S[i]= new Student(id,Nm,Br,Ph);

}
System.out.println("\nUSN"+"\tName"+"\tBranch"+"\tPhone");
{
S[i].display();
}
}
}
OUTPUT:
Enter the number of studens:3

Enter the details of Student no:1
Enter the university number:111
Name: ABC
Branch: CSE
Phone no: 9875653423
Enter the details of Student no: 2
Enter the university number: 222
Name: XYZ
Branch: ECS
Phone no: 875364264
Enter the details of Student no: 3
Enter the university number: 333
Name: MNO
Branch: EE
Phone no: 7734342343

USN Name Branch Phone

111 ABC CSE 9875653423
222 XYZ ECS 875364264
333 MNO EE 7734342343
1b) StackDemo.java
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.InputStreamReader;
class StackDemo {
private static final int capacity = 3;
intarr[] = new int[capacity];
int top = -1;
public void push(intpushedElement) {
if (top < capacity - 1) {
top++;
arr[top] = pushedElement;
System.out.println("Element "+pushedElement+" is pushed into Stack!");
}else {
System.out.println("Stack Overflow !");
}
}public void pop() {
if (top >= 0) { top--;
System.out.println("Pop operation is sucsuccessfull !");
System.out.print("and popped element is :"+ arr[top+1]);
}else {
System.out.println("Stack Underflow !");
}
}public void printElements() {
if (top >= 0) {
System.out.println("Elements in stack :");
for (inti = 0; i<= top; i++) {
System.out.println(arr[i]); }
}else{
System.out.println(" Stack is empty");
}
}
}
Lab.java
public class lab {
public static void main(String[] args) {
StackDemoStackDemo = new StackDemo();
Scanner in=new Scanner(System.in);

while(true){
System.out.println("\nEnter Your Choice");
System.out.print("1.PUSH \n2.POP \n3.DISPLAY \n");
int Choice=in.nextInt();
switch(Choice){
case 1: System.out.println("Enter Number to be pushed:-");
int Number =in.nextInt();
StackDemo.push(Number);
break;
case 2: StackDemo.pop();
break;
case 3: StackDemo.printElements();
break;
default:System.out.println("Invalid Choice");
}
}
}
}
OUTPUT:
Enter Your Choice
1.PUSH
2.POP
3.DISPLAY
1
Enter Number to be pushed:-
11
Element 11 is pushed into Stack!
Enter Your Choice
1.PUSH
2.POP
3.DISPLAY
1
22
Enter Your Choice
1.PUSH
2.POP
3.DISPLAY
1
22
Enter Your Choice

1.PUSH
2.POP
3.DISPLAY
1
33
Stack Overflow !
Enter Your Choice
1.PUSH
2.POP
3.DISPLAY
3
Elements in stack :
11
22
22
Enter Your Choice
1.PUSH
2.POP
3.DISPLAY
2
Pop operation is sucsuccessfull !
and popped element is :22
Enter Your Choice
1.PUSH
2.POP
3.DISPLAY
2
Enter Your Choice
1.PUSH
2.POP
3.DISPLAY
2
Enter Your Choice
1.PUSH
2.POP
3.DISPLAY
2
Stack Underflow !

2. a) Design a superclass called Staff with details as StaffId, Name, Phone, Salary.
Extend this class by writing three subclasses namely Teaching (domain,
publications),Technical (skills), and Contract (period). Write a Java program to read
and display atleast 3 staff objects of all three categories.
b) Write a Java class called Customer to store their name and date_of_birth. The
date_of_birth format should be dd/mm/yyyy. Write methods to read customer data as
<name, dd/mm/yyyy> and display as <name, dd, mm, yyyy> using StringTokenizer
class considering the delimiter character as “/”.
PROGRAM:
2a) Staff.java
class Staff{
privateintStaffId;
private String Name;
private String Phone;
privatelongSalary;
public Staff(intstaffId,Stringname,Stringphone,longsalary){
StaffId = staffId;
Name = name;
Phone = phone;
Salary = salary;
}
publicvoid Display(){
System.out.print("\t"+StaffId+"\t"+Name+"\t"+Phone+"\t"+Salary);
}
}
class Teaching extends Staff{
privatestatic String phone;
private String Domain;
privateintPublications;
public Teaching(intstaffId, String name, String phophone,
longsalary, String domain, intpublications){
super(staffId, name, phone, salary);
Domain = domain;
Publications = publications;
}
super.Display();
System.out.print("\t\t"+Domain+"\t"+Publications+"\t"+"--"+"\t"+"--");
}
}
class Technical extends Staff{

private String Skills;

public Technical(intstaffId, String name, String phone,
longsalary, String skills) {
Skills = skills;
}
super.Display();
System.out.print("\t\t--"+"\t\t"+"--"+"\t"+Skills+"\t"+"--");
}
}
class Contract extends Staff{
privateintPeriod;
public Contract(intstaffId, String name, String phone,
longsalary, intperiod) {
this.Period = period;
}
super.Display();
System.out.print("\t\t--"+"\t\t"+"--"+"\t\t"+"--"+"\t\t"+Period);
}
}
Lab.java
publicclass Lab {
publicstaticvoid main(String[] args) {
Staff staff[]=new Staff[3];
staff[0]=new Teaching(1,"Narendr","271173",90000,"CSE",3);
staff[1]=new Technical(2,"Ara","271172",2000,"Server Admin");
staff[2]=new Contract(3,"Rahul","271174",9000,3);
System.out.println("Staff
ID\tName\t\tPhone\t\tSalary\t\tDomain\tPublication\tSkills\tPeriod");
for(inti=0;i<3;i++){
staff[i].Display();
System.out.println();
}
}
}

OUTPUT:
Staff ID Name Phone Salary Domain Publication Skills
1 Narendr null 90000 CSE 3 -- --
2 Ara 271172 2000 -- -- Server Admin -- 3
3 Rahul 271174 9000 -- -- -- 3
2b) Customer.java
importjava.util.Scanner;
importjava.util.StringTokenizer;
class Customer{
private String name;
private String date_of_birth;
public Customer(String name, String date_of_birth) {
super();
this.name = name;
this.date_of_birth = date_of_birth;
}public Customer (){
}
publicvoidreadData(String name, String date_of_birth){
this.name = name;
this.date_of_birth = date_of_birth;
}publicvoiddisplayData(){
StringTokenizerst=new
StringTokenizer(this.date_of_birth,"/");
System.out.print(this.name+",");
while(st.hasMoreTokens()){
System.out.print(st.nextToken()+" ");
}
}
}
Lab.java
importjava.util.Scanner;
publicclass Lab {
publicstaticvoid main(String[] args) {
Scanner in=newScanner(System.in);
System.out.println("Enter Name :-");
String name=in.nextLine();
System.out.println("Enter Date of birth:-");
String date=in.next();
Customer customer=newCustomer();
customer.readData(name, date);
customer.displayData();
}
}

OUTPUT
Enter Name :-
abc
Enter Date of birth:-
04-12-1992
abc,04-12-1992
3 a) Write a Java program to read two integers a and b. Compute a/b and print, when b
is not zero. Raise an exception when b is equal to zero.
b) Write a Java program that implements a multi-thread application that has three
threads. First thread generates a random integer for every 1 second; second thread
computes the square of the number and prints; third thread will print the value of cube
of the number.
PROGRAM:
3a)
Division.java
package threea;
Import java.util.Scanner;
Public class division {
Public static void main(String[] args)

{
Scanner in= new Scanner(System.in);
System.out.println("Enter two numbers:");
double number1 = in.nextDouble();
double number2 = in.nextDouble();
double quotient= (number1/number2);
System.out.println("The quotient of\t"+ quotient);
if (number2!=0)
{
System.out.println("The value of number1\t"+number1);
System.out.println("The value of number2\t"+ number2);
}
else{
System.out.println("not valid");
}
}
}
OUTPUT:
Enter two numbers:
6
2
The quotient of 3.0
The value of number1 6.0

The value of number2 2.0

3b)
Multithreaded.java
package threeb;
import java.util.*;
public class MultiTreaded
{public static void main(String[] args)
{
/*FirstThfirstThread = new FirstTh();
Thread t1 = new Thread(firstThread);
t1.start();*/
Thread t1 = new Thread(new FirstTh());
t1.start();//starts the execution of the thread.JVM calls the run() method
on the thread
}
}
FirstTh.java
package threeb;
import java.util.*;
public class FirstTh extends Thread
{ public void run() //is used to perform action for a thread.
{
intnum = 0;
Random r = new Random();
try
{ for (inti = 0; i< 5; i++)
{ num = r.nextInt(100);
System.out.println("Main Thread Started and Generated Number is " + num);
Square sq = new Square(num);
Thread t2 = new Thread(sq);
t2.start();
/* Thread t2 = new Thread(new Square(num));
t2.start();*/
Thread t3 = new Thread(new Cube(num));
t3.start();
Thread.sleep(1000);
System.out.println("---------------------");
}
}catch (Exception ex)
{
System.out.println(ex.getMessage());
}
}
}

Cube.java
package threeb;
import java.util.*;
public class Cube implements Runnable
{
public int x;
public Cube(int x)
{
this.x = x;
}
public void run() // is used to perform action for a thread.
{
System.out.println("From Third thread - Cube of " +x + " is: " + x * x * x);
}
}
Square.java
packagethreeb;
importjava.util.*;
public class Square implements Runnable
{
publicint x;
public Square(int x)
{ this.x = x;
}
public void run()
{
System.out.println("From Second thread - Square of "+ x + " is: " + x * x);
}
}
OUTPUT:
Main Thread Started and Generated Number is 15
From Second thread - Square of 15 is: 225
From Third thread - Cube of 15 is: 3375
---------------------
---------------------
---------------------


---------------------
---------------------
4. 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 non graph sheet. The elements can be read
from a file or can be generated using the random number generator. Demonstrate using
Java how the divide and-conquer method works along with its time complexity analysis:
worst case, average case and best case.
Program:
package quick;
import java.util.Random;
public class quick {
int a[]= newint[100000];
Scanner in = new Scanner(System.in);
long start, end;
System.out.println("*********QUICK SORT PROGRAM *********");
System.out.println("Enter the number of elements to be sorted");
int n = in.nextInt();
Random rand= new Random();
for(inti=0;i<n;i++)
a[i]=rand.nextInt(100);
System.out.println("Array elements to be sorted are");
for(inti=0; i<n; i++)
System.out.print(a[i]+" ");
a[n]=999;
start=System.nanoTime();
quicksort(a,0,n-1);
end=System.nanoTime();
System.out.println("\nThe sorted elements are");
for(inti=0; i<n; i++)
System.out.println("The time taken to sort is "+(end-start)+"ns");
System.out.println("******** ******************* *******");
}static void quicksort(inta[],intp, intq){
int j;
if(p<q){
j=partition(a,p,q); // partition array into parts
quicksort(a,p,j-1); // sort left part of array

quicksort(a,j+1,q); // sort right part of array

}
}static int partition(inta[],intm, intp){
int v, i, j;
v=a[m]; // first element is pivot element
i=m;
j=p;
while(i<= j){
while(a[i] <= v)
i++;
while(a[j] >v)
j--;
if(i<j)
interchange (a,i,j); //swap the contents
}
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;
}
}
OUTPUT:
1) ********** QUICK SORT PROGRAM *********
Enter the number of elements to be sorted
20
Array elements to be sorted are
35 93 25 35 92 97 43 88 92 0 35 57 78 32 59 56 98 4 71 9
The sorted elements are
0 4 9 25 32 35 35 35 43 56 57 59 71 78 88 92 92 93 97 98
The time taken to sort is 31278ns
******** *********************** *******
2) ********** QUICK SORT PROGRAM *********
10
36 64 13 82 9 19 53 0 72 23
0 9 13 19 23 36 53 64 72 82
******** *********************** *******

5. 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 non graph sheet. The elements can be read
from a file or can be generated using the random number generator. Demonstrate using
Java how the divide and-conquer method works along with its time complexity analysis:
worst case, average case and best case.
PROGRAM:
package merge;
import java.util.Random;
public class merge {
int a[]= new int[100000];
long start, end;
System.out.println("********** MERGE SORT PROGRAM *********");
System.out.println("Enter the number of elements to be sorted");
Random rand= new Random();
a[i]=rand.nextInt(100);
System.out.println("Array elements to be sorted are");
for(int i=0; i<n; i++)
start=System.nanoTime();
mergesort(a,0,n-1);
end=System.nanoTime();
System.out.println("\nThe sorted elements are");
for(int i=0; i<n; i++)
System.out.println("The time taken to sort is "+(end-start)+"ns");
System.out.println("******** ********************** *******");
}
static void mergesort(int a[], int low, int high){
int mid;
if(low < high){
mid = (low+high)/2;
mergesort(a, low, mid);
mergesort(a, mid+1, high);
merge(a, low, mid, high);
}
}
static void merge(int a[], int low, int mid, int high){
int i, j, h, k, b[]= new int[100000];

h=low; i=low; j=mid+1;

while((h<=mid) && (j<=high)){
if(a[h] < a[j]){
b[i] = a[h]; h=h+1;
}
else
{
b[i] = a[j]; j=j+1;
}
i = i+1;
}
if(h > mid){
for(k=j; k<=high; k++){
b[i] = a[k]; i = i+1;
}
}
else
{
for(k=h; k<=mid; k++){
b[i] = a[k]; i = i+1;
}
}
for(k=low; k<= high; k++)
a[k] = b[k];
}
}
OUTPUT:
1)********** MERGE SORT PROGRAM *********
10
34 83 89 21 62 36 48 90 36 85
21 34 36 36 48 62 83 85 89 90
******** *********************** *******
2) ********** MERGE SORT PROGRAM *********
20
56 55 12 91 83 43 62 93 70 33 54 45 57 51 35 17 0 67 23 39
0 12 17 23 33 35 39 43 45 51 54 55 56 57 62 67 70 83 91 93

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

6. Implement in Java, the 0/1 Knapsack problem using (a) Dynamic Programming
method (b)
Greedy method.
PROGRAM:
6a)
public class Lab6A {
int v[][]=new int[10][10], w[]=new int[10], p[]=new int[10];
int i, j;
System.out.println("************* KNAPSACK PROBLEM ***********");
System.out.println("Enter the total number of items: ");
System.out.println("Enter the weight of each item: ");
for(i=1;i<=n;i++)
w[i] = in.nextInt();
System.out.println("Enter the profit of each item: ");
for(i=1;i<=n;i++)
p[i] = in.nextInt();
System.out.println("Enter the knapsack capacity: ");
int m= in.nextInt();
displayinfo(m,n,w,p);
knapsack(m,n,w,p,v);
System.out.println("The contents of the knapsack table are");
for(i=0; i<=n; i++){
for(j=0; j<=m; j++){
System.out.print(v[i][j]+" " );
}
}
optimal(m,n,w,v); //call optimal function
}
static void displayinfo(int m,int n,int w[],int p[]){
System.out.println("Entered information about knapsack problem are");
System.out.println("ITEM\tWEIGHT\tPROFIT");
for(int i=1; i<=n; i++)
System.out.println(i+"\t"+w[i]+"\t"+p[i]);
System.out.println("Capacity = "+m);
}
static void knapsack(int m,int n,int w[],int p[],int v[][]){
for(int i=0; i<=n; i++){
for(int j=0; j<=m; j++){

if(i==0 ||j==0)
v[i][j]=0;
else if(j < w[i])
v[i][j]=v[i-1][j];
else
v[i][j]=max(v[i-1][j], v[i-1][j-w[i]]+p[i]);
}
}
}
private static int max(int i, int j) {
if(i>j)
return i;
else return j;
}
static void optimal(int m,int n,int w[],int v[][]){
int i = n, j = m, item=0;
int x[]=new int[10];
while( i != 0 && j != 0){
if(v[i][j] != v[i-1][j]){
x[i] = 1;
j = j-w[i];
}
i = i-1;
}
System.out.println("Optimal solution is :"+ v[n][m]);
System.out.println("Selected items are: ");
for(i=1; i<= n;i++)
if(x[i] == 1){
System.out.print(i+" ");
item=1;
}
if(item == 0)
System.out.println("NIL\t Sorry ! No item can be placed in Knapsack");
System.out.println("\n********* *********************** *************");
}
}
OUTPUT:
**************** KNAPSACK PROBLEM ****************
Enter the total number of items:
4
Enter the weight of each item:
2312
Enter the profit of each item:
12 10 15 20

Enter the knapsack capacity:

5
Entered information about knapsack problem are
ITEM WEIGHT PROFIT
1 2 12
2 3 10
3 1 15
4 2 20
Capacity = 5
The contents of the knapsack table are
000000
0 0 12 12 12 12
0 0 12 12 12 22
0 15 15 27 27 27
0 15 20 35 35 47
Optimal solution is :47
Selected items are:
134
********* ******************************* *************
6b)
public class Lab6B {
float w[]=new float[10],p[]=new float[10];
float ratio[]=new float[10];
int i;
System.out.println("********* KNAPSACK PROBLEM *******");
System.out.println("Enter the total number of items: ");
System.out.println("Enter the weight of each item: ");
for(i=1;i<=n;i++)
w[i] = in.nextFloat();
System.out.println("Enter the profit of each item: ");
for(i=1;i<=n;i++)
p[i] = in.nextFloat();
System.out.println("Enter the knapsack capacity: ");
int m= in.nextInt();
for(i=1;i<=n;i++)
ratio[i]=p[i]/w[i];
System.out.println("Information about knapsack problem are");
displayinfo(n,w,p,ratio);
System.out.println("Capacity = "+m);

sortArray(n,ratio,w,p);
System.out.println("\nDetails after sorting items based on
Profit/Weight ratio in descending order: ");
displayinfo(n,w,p,ratio);
knapsack(m,n,w,p);
System.out.println("*************************************");
}
static void sortArray(int n,float ratio[],float w[],float p[]){
int i,j;
for(i=1; i<=n; i++)
for(j=1; j<=n-i; j++){
if(ratio[j]<ratio[j+1]){
float temp=ratio[j];
ratio[j]=ratio[j+1];
ratio[j+1]=temp;
temp=w[j];
w[j]=w[j+1];
w[j+1]=temp;
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
}
static void display info(int n,float w[],float p[],float ratio[]){
System.out.println("ITEM\tWEIGHT\tPROFIT\tRATIO(PROFIT/WEIGHT)");
for(int i=1; i<=n; i++)
System.out.println(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]);
System.out.println("\nThe result is = ");
for(i=1; i<=n; i++)
System.out.print("\t"+x[i]);
System.out.println("\nMaximum profit is = "+tp);
}
}
OUTPUT:
**************** KNAPSACK PROBLEM ****************
Enter the total number of items:
4
Enter the weight of each item:
3354
Enter the profit of each item:
6 4 11 16
Enter the knapsack capacity:
6
Information about knapsack problem are
ITEM WEIGHT PROFIT RATIO(PROFIT/WEIGHT)
1 3.0 6.0 2.0
2 3.0 4.0 1.3333334
3 5.0 11.0 2.2
4 4.0 16.0 4.0
Capacity = 6
Details after sorting items based on Profit/Weight ratio in
descending order:
ITEM WEIGHT PROFIT RATIO(PROFIT/WEIGHT)
1 4.0 16.0 4.0
2 5.0 11.0 2.2
3 3.0 6.0 2.0
4 3.0 4.0 1.3333334
The result is =
1.0 0.4 0.0 0.0
Maximum profit is = 20.4
7. From a given vertex in a weighted connected graph, find shortest paths to other
vertices using Dijkstra's algorithm. Write the program in Java.
PROGRAM:
package dj;
public class dj {

int i, j;
int dist[]=new int[10], visited[]=new int[10];
int cost[][]=new int[10][10], path[]=new int[10];
System.out.println("**** DIJKSTRA'S ALGORITHM ******");
System.out.println("Enter the number of nodes: ");
System.out.println("Enter the cost matrix");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j] = in.nextInt();
System.out.println("The entered cost matrix is");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
System.out.print(cost[i][j]+"\t");
}
}
System.out.println("Enter the source vertex: ");
int sv = in.nextInt();
dij(cost,dist,sv,n,path,visited);
printpath(sv,n,dist,path,visited );
System.out.println("\n********* *************** *********");
}
static void dij(int cost[][],int dist[],int sv,int n,int path[],int visited[])
{
int count = 2,min,v=0;
visited[i]=0;
dist[i] = cost[sv][i];
if(cost[sv][i] == 999)
path[i] = 0;
else
path[i] = sv;
}
visited[sv]=1;
while(count<=n){
min = 999;
for(int w=1; w<=n; w++)
if((dist[w]< min) && (visited[w]==0))
{
min = dist[w];

v = w;
}
visited[v] = 1;
count++;
for(int w=1; w<=n; w++){
if((dist[w]) >(dist[v] + cost[v][w]))
{
dist[w] = dist[v] + cost[v][w];
path[w] = v;
}
}
}
}
static void printpath(int sv,int n,int dist[],int path[],int visited[]){
for(int w=1; w<=n; w++){
if(visited[w] == 1 && w != sv){
System.out.println("The shortest distance between ");
System.out.println(sv+"-> ="+w+" is :"+ dist[w]);
int t=path[w];
System.out.println("The path is:");
System.out.print(" "+w);
while(t != sv){
System.out.print("<-->"+t);
t=path[t];
}
System.out.print("<-->"+sv);
}
}
}
}
OUPUT:
Enter the number of nodes:
4
Enter the cost matrix
0 3 1 999
3 0 999 1
1 999 0 2
999 1 2 0
The entered cost matrix is
0 3 1 999
3 0 999 1
1 999 0 2
999 1 2 0
Enter the source vertex:

1
The shortest distance between
1-> =2 is :3
The path is:
2<-->1The shortest distance between
1-> =3 is :1
The path is:
3<-->1The shortest distance between
1-> =4 is :3
The path is:
4<-->3<-->1
********* *************** *********
8. Find Minimum Cost Spanning Tree of a given connected undirected graph using
Kruskal's algorithm. Use Union-Find algorithms in your program.
PROGRAM:
package kruskal;
public class kk {
int cost[][]=new int[10][10];
int i, j,mincost=0;
System.out.println("********* KRUSKAL'S ALGORITHM *******");
System.out.println("Enter the number of nodes: ");
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cost[i][j] = in.nextInt();
}
}System.out.println("The entered cost matrix is");
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
System.out.print(cost[i][j]+"\t");
}System.out.println();
}
mincost=kruskals(n,mincost,cost);
System.out.println("The minimum spanning tree cost is: ");
System.out.println(mincost);
System.out.println("********* ****************** **********");
}
static int kruskals(int n,int mincost,int cost[][] ) {
int ne = 1,a=0,u=0,b=0,v=0,min;
int parent[]=new int[10];

while(ne < n){

min=999;
for(int j=1; j<=n; j++){
if(cost[i][j] < min){
min = cost[i][j];
a=u=i;
b=v=j;
}
}
}
while(parent[u]>0)
u = parent[u];
while(parent[v]>0)
v = parent[v];
if(u != v)
{
System.out.println("Edge Number \t" +ne+ "\t from Vertex \t" +a +" to Vertex \t"+b+"-
minimum_cost:"+min+"\n");
mincost += min;
parent[v] = u;
}
cost[a][b] = cost[b][a] = 999;
}
return mincost;
}
}
OUTPUT:
********* KRUSKAL'S ALGORITHM *******
Enter the number of nodes:
6
0 3 999 999 6 5
3 0 1 999 999 4
999 1 0 6 999 4
999 999 6 0 8 5
6 999 999 8 0 2
544520
0 3 999 999 6 5
3 0 1 999 999 4
999 1 0 6 999 4
999 999 6 0 8 5
6 999 999 8 0 2

5 4 4 5 2 0
Edge Number 1 from Vertex 2 to Vertex 3-minimum_cost:1
The minimum spanning tree cost is: 15
********* ****************** **********
9. Find Minimum Cost Spanning Tree of a given connected undirected graph using
Prim's algorithm.
PROGRAM:
package primsman;
import java.util.*;
public class prims {
public int isVisited[] = new int[15];
public int cost[][] = new int[10][10];
public int minimum_cost;
public void calc(int n)
{
//int flag[] = new int[n+1];
int i,j,min=999,num_edges=1,a=1,b=1,minpos_i=1,minpos_j=1;
while(num_edges<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(this.cost[i][j]<min)
if(this.isVisited[i]!=0)
{
min= this.cost[i][j];
a=minpos_i=i;
b=minpos_j=j;
}
if(this.isVisited[minpos_i]==0||this.isVisited[minpos_j]==0)
{ System.out.println("Edge Number \t" +num_edges+ "\t from Vertex \t" +a
+" to Vertex \t"+b+"-minimum_cost:"+min+"\n");
this.minimum_cost=this.minimum_cost+min;
num_edges=num_edges+1;
this.isVisited[b]=1;
}
this.cost[a][b]= this.cost[b][a]=999;
}
}

public static void main(String args[])

{
int nodes,i,j;
System.out.println("Enter the number of nodes\n");
nodes = in.nextInt();
prims p = new prims();
System.out.println("Enter the Cost matrix weights:\n");
for(i=1;i<=nodes;i++)
for(j=1;j<=nodes;j++)
{ p.cost[i][j]=in.nextInt();
if(p.cost[i][j]==0)
p.cost[i][j]=999;
}
p.isVisited[1]=1;
p.calc(nodes);
}
}
OUTPUT:
Enter the number of nodes
6
Enter the Cost matrix weights:
0 3 999 999 6 5
3 0 1 999 999 4
999 1 0 6 999 4
999 999 6 0 8 5
6 999 999 8 0 2
544520
Total cost is:15
10. Write Java programs to
(a) Implement All-Pairs Shortest Paths problem using Floyd's algorithm.
(b) Implement Travelling Sales Person problem using Dynamic programming.
Program:
package flyod;
public class floyd {

int a[][]=new int[10][10];

int i, j;
System.out.println("***********FLOYD'SALGORITHM**********");
System.out.println("Enter the number of vertices: ");
System.out.println("Enter the adjacency matrix");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j] = in.nextInt();
System.out.println("Entered adjacency matrix is: ");
for(i=1;i<=n;i++) {
for(j=1; j<=n; j++) {
System.out.print(a[i][j]+"\t");
}
System.out.println();}
floyd(a,n);
System.out.println("All pair shortest path matrix:");
for (i=1; i<=n; i++) {
for (j=1; j<=n; j++)
System.out.print(a[i][j]+"\t");
}
System.out.println("************ ********* **************");
}
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] = min(a[i][j], a[i][k] + a[k][j]);
}
}
static int min(int a,int b) {
if(a>b)
return b;
else
return a;
}
}
OUTPUT:
***********FLOYD'SALGORITHM**********
Enter the number of vertices:
5
Enter the adjacency matrix

0 999 55 45 55
999 35 89 44 65
58 75 89 25 999
48 32 45 66 999
999 55 45 88 45
Entered adjacency matrix is:
0 999 55 45 55
999 35 89 44 65
58 75 89 25 999
48 32 45 66 999
999 55 45 88 45
All pair shortest path matrix:
0 77 55 45 55
92 35 89 44 65
58 57 70 25 113
48 32 45 66 97
103 55 45 70 45
************ ********* **************
10 b) Travelling Salesman Problem
package tsp;
public class tsp {
int c[][]=new int[10][10], tour[]=new int[10];
int i, j,cost;
System.out.println("**** TSP DYNAMIC PROGRAMMING *******");

System.out.println("Enter the number of cities: ");
if(n==1) {
System.out.println("Path is not possible");
System.exit(0);
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
c[i][j] = in.nextInt();
System.out.println("The entered cost matrix is");
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
System.out.print(c[i][j]+"\t");
}

}
for(i=1;i<=n;i++)
tour[i]=i;
cost = tspdp(c, tour, 1, n);
System.out.println("The accurate path is");
for(i=1;i<=n;i++)
System.out.print(tour[i]+"->");
System.out.println("1");
System.out.println("The accurate mincost is "+cost);
System.out.println("******* ************* ***************");
}
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]);
}
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;
}
}
OUTPUT:
*** TSP DYNAMIC PROGRAMMING *******
Enter the number of cities:
4
0 10 15 20
5 0 9 10
6 13 0 12
8890
0 10 15 20

5 0 9 10
6 13 0 12
8 8 9 0
The accurate path is
1->2->4->3->1
The accurate mincost is 35
******* ************* ***************
11. Design and implement in Java 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.
Program:
public class Lab10A {
static int c=0;
int w[]=new int[10];
int n, d, i, sum=0;
int x[]=new int[10];
Scanner in=new Scanner(System.in
System.out.println("********** SUBSET PROBLEM ************");
System.out.println("Enter the number of elements: ");
n=in.nextInt();
System.out.println("Enter the elements in increasing order");
for(i=0;i<n;i++)
w[i]=in.nextInt();
System.out.println("Enter the value of d: ");
d=in.nextInt();
for(i=0;i<n;i++)
sum=sum+w[i];
System.out.println("SUM ="+sum);
if(sum < d || w[0] > d){
System.out.println("Subset is not possible ! ");
System.out.println("********** *********** *************");
System.exit(0);
}
subset(0,0,sum,x,w,d);
if(c==0)
System.out.println("Subset is not possible ! ");
System.out.println("\n********** ********* *************");
}
static void subset(int cs, int k, int r,int x[],int w[],int d){
x[k] = 1;
if(cs+w[k] == d) {

c++;
System.out.print("\nSolution "+c+" is {");
for(int i=0;i<=k;i++)
if(x[i] == 1) {
System.out.print(w[i]+" ");
}
System.out.print("}");
}
else if((cs + w[k] + w[k+1]) <= d)
subset(cs + w[k], k+1, r-w[k],x,w,d);
if((cs + r - w[k]) >= d && (cs + w[k+1]) <= d) {
Department of CSE,SIT,Mangaluru Page 35
x[k] = 0;
subset(cs, k+1, r-w[k],x,w,d);
}
}
}
OUTPUT:
*********** SUBSET PROBLEM ************
Enter the number of elements:
5
Enter the elements in increasing order:
12368
Enter the value of d:
9
SUM =20
Solution 1 is {1 2 6 }
Solution 2 is {1 8 }
Solution 3 is {3 6 }
********** ****************** *************
12. Design and implement in Java to find all Hamiltonian Cycles in a connected
undirected Graph G of n vertices using backtracking principle.
Program:
public class Lab10B {
static int n;
System.out.println("Enter no. of vertices");
n=in.nextInt();
int graph[][]=new int[10][10];

System.out.println("Enter adjacency matrix of graph");

for(int j=0;j<n;j++)
graph[i][j] =in.nextInt();
System.out.println("Entered adjacency matrix of graph is");
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
System.out.print("\t"+graph[i][j]);
}
}
hamCycle(graph);
System.out.println("\n*********************************\n");
}
static void printSolution(int path[]){
System.out.println("Solution Exists:");
System.out.println(" Following is one Hamiltonian Cycle ");
for (int i = 0; i <n; i++)
System.out.println(path[i]);
System.out.println(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;
}
/* A recursive utility function to solve Hamiltonian cycle
problem */
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;
}
/* This function solves the Hamiltonian Cycle problem using
Backtracking. It mainly uses hamCycleUtil() to solve the problem.
It returns false if there is no Hamiltonian Cycle possible,
otherwise return true and prints the path.This function prints
one of the feasible solutions. */
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){
System.out.println("\nSolution does not exist");
return false;
}
printSolution(path);
return true;
}
}
OUTPUT 1:
*******************Hamiltonian cycle*****************
Enter no. of vertices
5
Enter adjacency matrix of graph
01010101110100111001
01110
Entered adjacency matrix of graph is
01010
10111
01001
11001
01110
Solution Exists:
Following is one Hamiltonian Cycle
0 -->1 -->2 -->4 -->3 -->0
******************************************************
OUTPUT 2:
*******************Hamiltonian cycle*****************
Enter no. of vertices
5
Enter adjacency matrix of graph
010101011101001110000

1100
Entered adjacency matrix of graph is
01010
10111
01001
11000
01100
Solution does not exist
******************************************************

Angadi Institute of Technology and Management

Uploaded by

Copyright:

Available Formats

Angadi Institute of Technology and Management

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Angadi Institute of Technology and Management

Uploaded by

Copyright:

Available Formats

Design and Analysis of Algorithm Lab

System.out.println("Enter the number of studens:");

Student[] S= new Student[n];

Dept. Of CSE, AITM Belagavi Page 1

System.out.println("Enter the university number:");

S[i]= new Student(id,Nm,Br,Ph);

Enter the number of studens:3

Dept. Of CSE, AITM Belagavi Page 2

USN Name Branch Phone

Dept. Of CSE, AITM Belagavi Page 3

Dept. Of CSE, AITM Belagavi Page 4

Dept. Of CSE, AITM Belagavi Page 5

Dept. Of CSE, AITM Belagavi Page 6

private String Skills;

Dept. Of CSE, AITM Belagavi Page 7

Dept. Of CSE, AITM Belagavi Page 8

Public static void main(String[] args)

Dept. Of CSE, AITM Belagavi Page 9

The value of number2 2.0

Dept. Of CSE, AITM Belagavi Page 10

Dept. Of CSE, AITM Belagavi Page 11

From Third thread - Cube of 62 is: 238328

Dept. Of CSE, AITM Belagavi Page 12

quicksort(a,j+1,q); // sort right part of array

Dept. Of CSE, AITM Belagavi Page 13

Dept. Of CSE, AITM Belagavi Page 14

h=low; i=low; j=mid+1;

Dept. Of CSE, AITM Belagavi Page 15

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

Dept. Of CSE, AITM Belagavi Page 16

Dept. Of CSE, AITM Belagavi Page 17

Enter the knapsack capacity:

Dept. Of CSE, AITM Belagavi Page 18

Dept. Of CSE, AITM Belagavi Page 19

Dept. Of CSE, AITM Belagavi Page 20

Dept. Of CSE, AITM Belagavi Page 21

Dept. Of CSE, AITM Belagavi Page 22

Dept. Of CSE, AITM Belagavi Page 23

while(ne < n){

Dept. Of CSE, AITM Belagavi Page 24

Dept. Of CSE, AITM Belagavi Page 25

public static void main(String args[])

Dept. Of CSE, AITM Belagavi Page 26

int a[][]=new int[10][10];

Dept. Of CSE, AITM Belagavi Page 27

System.out.println("**** TSP DYNAMIC PROGRAMMING *******");

Dept. Of CSE, AITM Belagavi Page 28

Dept. Of CSE, AITM Belagavi Page 29

Dept. Of CSE, AITM Belagavi Page 30

Dept. Of CSE, AITM Belagavi Page 31

System.out.println("Enter adjacency matrix of graph");

Dept. Of CSE, AITM Belagavi Page 32

Dept. Of CSE, AITM Belagavi Page 33

Dept. Of CSE, AITM Belagavi Page 34

You might also like

********* *

System.out.println(" TSP DYNAMIC PROGRAMMING ***");