DAA LAB MANUAL

SUBJECT: DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY

SUBJECT CODE: 18CSL47

1.a. Create a Java class called Student with the following details as variables within it. (i) USN (ii)
Name (iii) Programme (iv) Phone. Write a Java program to create n Student objects and print the
USN, Name, Programme, and Phone of these objects with suitable headings.

import java.util.Scanner;
class student
{
String NAME;
String USN;
String BRANCH;
long PHONE;
void insert(String name,String usn,String branch,long phone)
{
NAME=name;
USN=usn;
BRANCH=branch;
PHONE=phone;
}
void display()
{
System.out.println(NAME+"\t"+USN+"\t"+BRANCH+"\t"+PHONE);
}
public static void main(String args[])
{
String name,reg,branch;
long phone;
int n;

1
DAA LAB MANUAL

Scanner scan=new Scanner(System.in);

System.out.println("Enter no.of students");
n=scan.nextInt();
student[] s=new student[n];
int i;
for(i=0;i<n;i++)
{
s[i]=new student();
System.out.println("enter name,usn,branch,phone of student"+(i+1));
name=scan.next();
reg=scan.next();
branch=scan.next();
phone=scan.nextLong();
s[i].insert(name,reg,branch,phone);
}
System.out.println("NAME\tUSN\tBRANCH\tPHONE");
for(i=0;i<n;i++)
{
s[i].display();
}
}
}

1.b. Write a Java program to implement the Stack using arrays. Write Push(), Pop(), and Display()
methods to demonstrate its working.

import java.util.Scanner;
class Stack
{
int i,top=-1,max=50;
int a[]=new int[max];

2
DAA LAB MANUAL

void push(int ele)

{
if(top==max-1)
System.out.println("Stack overflow");
else
a[++top]=ele;
}

void pop()
{
if(top==-1)
System.out.println("Stack underflow");
else
{
System.out.println("Poped element is "+a[top]);
top--;
}
}

void display()
{
if(top==-1)
System.out.println("Stack underflow");
else
{
System.out.print("Stack elements are: ");
for(int i=0;i<=top;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}

3
DAA LAB MANUAL

class StackDemo
{
public static void main(String args[])
{
Stack s=new Stack();
int ele,ch;
Scanner scan=new Scanner(System.in);
System.out.println("MENU items are");
System.out.println("1.PUSH 2.POP 3.DISPLAY 4.EXIT ");
while(true)
{
System.out.println("Enter your choice");
ch=scan.nextInt();
switch(ch)
{
case 1:System.out.println("Enter the element to be pushed");
ele=scan.nextInt();
s.push(ele);
break;
case 2:s.pop();
break;
case 3:s.display();
break;
case 4:System.exit(0);
}
}
}
}

4
DAA LAB MANUAL

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 at least 3 staff objects of all three
categories.

import java.util.Scanner;
class Staff
{
int id,sal;
String name;
Long phn;
void read()
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the ID, name,phone no,salary");
id=sc.nextInt();
name=sc.next();
phn=sc.nextLong();
sal=sc.nextInt();

}
void display()
{
System.out.print(id+"\t"+name+"\t"+phn+"\t"+sal);
}
}
class Teaching extends Staff
{
String dmn,pub;
void read()
{
super.read();

5
DAA LAB MANUAL

Scanner sc=new Scanner(System.in);

System.out.println("Enter the domain,publication");
dmn=sc.next();
pub=sc.next();
}
void display()
{
super.display();
System.out.println("\t"+dmn+"\t"+pub);
}
}
class Technical extends Staff
{
String skl;
void read()
{
super.read();
System.out.println("Enter the skill");
Scanner sc=new Scanner(System.in);
skl=sc.next();
}
void display()
{
super.display();
System.out.println("\t"+skl);
}
}
class Contract extends Staff
{
String per;
void read()

6
DAA LAB MANUAL

{
super.read();
System.out.println("Enter the period");
Scanner sc=new Scanner(System.in);
per=sc.next();
}

void display()
{
super.display();
System.out.println("\t"+per);
}
}
class StaffDemo
{
public static void main(String args[])
{
int i,n;
System.out.println("Enter the number of staffs");
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
Teaching T[]=new Teaching[n];
Technical TE[]=new Technical[n];
Contract C[]=new Contract[n];
for(i=0;i<n;i++)
{
T[i]=new Teaching();
TE[i]=new Technical();
C[i]=new Contract();
}
System.out.println("Enter the Teaching staffs details");

7
DAA LAB MANUAL

for(i=0;i<n;i++)
T[i].read();
System.out.println("Enter the Technical staffs details");
for(i=0;i<n;i++)
TE[i].read();
System.out.println("Enter the Contract staffs details");
for(i=0;i<n;i++)
C[i].read();
System.out.println("*********** Teaching staffs details ***********");
System.out.println("StaffId\tName\tPhone\t\tSalary\tDomain\tPublication");
for(i=0;i<n;i++)
T[i].display();
System.out.println("\n*********** Technical staffs details ***********");
System.out.println("StaffId\tName\tPhone\t\tSalary\tSkills");
for(i=0;i<n;i++)
TE[i].display();
System.out.println("\n********** Contract staffs details ***********");
System.out.println("StaffId\tName\tPhone\t\tSalary\tPeriod");
for(i=0;i<n;i++)
C[i].display();
}
}

2.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 and display as using
StringTokenizer class considering the delimiter character as “/”.

import java.util.Scanner;

import java.util.StringTokenizer;

class Customer

8
DAA LAB MANUAL

String name,dob;

void read()

System.out.println("Enter the customer name");

Scanner sc=new Scanner(System.in);

name=sc.next();

System.out.println("Enter the date of birth as dd/mm/yyyy");

dob=sc.next();

void display()

StringTokenizer st=new StringTokenizer(dob,"/");

System.out.print("<"+name);

while(st.hasMoreTokens())

System.out.print(",");

System.out.print(st.nextToken());

System.out.println(">");

public static void main(String[] args) {

9
DAA LAB MANUAL

System.out.println("Enter number of customers");

Scanner scan=new Scanner(System.in);

int n=scan.nextInt();

Customer c[]=new Customer[n];

for(int i=0;i<n;i++)

c[i]=new Customer ();

c[i].read();

System.out.println("Customers details are");

for(int i=0;i<n;i++)

System.out.println("Details of customer"+(i+1));

c[i].display();

3.a. Write a Java program to read two integers a andb. Compute a/b and print, when b is not zero.
Raise an exception when b is equal to zero.

public class Divide {

public static void main(String[] args)

10
DAA LAB MANUAL

int a,b,result;

Scanner input =new Scanner(System.in);

System.out.println("Input two integers");

a=input.nextInt();

b=input.nextInt();

try

result=a/b;

System.out.println("Result="+result);

catch(Exception e)

System.out.println("exception caught "+e);

3.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 andprints; third thread will print the value of cube of the number

import java.util.*;

11
DAA LAB MANUAL

class First extends Thread

int n;

First(int n)

this.n=n;

public void run()

int i,num;

Random r=new Random();

try

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

num=r.nextInt(100);

System.out.println("First thread generates number= "+num);

Thread.sleep(1000);

Thread t2=new Thread(new Second(num));

t2.start();

Thread t3=new Thread(new Third(num));

t3.start();

//Thread.sleep(1000);

12
DAA LAB MANUAL

catch(Exception e)

System.out.println("Exception occured: "+e);

class Second extends Thread

int n;

String name;

Second(int n)

this.n=n;

public void run()

System.out.println("second thread-Square of"+ n+ "is:"+(n*n));

class Third extends Thread

13
DAA LAB MANUAL

int n;

String name;

Third(int n)

this.n=n;

public void run()

System.out.println("third thread- Cube of"+ n +"is:"+(n*n*n));

public class MultithreadDemo

public static void main(String args[])

int n;

System.out.println("Enter n");

Scanner sc=new Scanner(System.in);

n=sc.nextInt();

Thread t1=new Thread(new First(n));

t1.start();

14
DAA LAB MANUAL

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.

import java.util.*;
class quick
{
int partition (int a[],int low,int high)
{
int p,i,j,temp;
p=a[low];
i=low;

j=high;
do
{
do{
i++;
}while(a[i]<p);
do
{
j--;
}while(a[j]>p);
if(i<j)
{
temp=a[i];

15
DAA LAB MANUAL

a[i]=a[j];
a[j]=temp;
}
}while(i<j);
temp=a[low];
a[low]=a[j];
a[j]=temp;
return j;
}

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

{
if(low<high)
{
int s=partition(a,low,high+1);
sort(a,low,s-1);
sort(a,s+1,high);
}
}
public static void main(String[] args)
{
int i,n;
System.out.println("Enter the array size");
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
Random r=new Random();
quick q=new quick();
int a[]=new int[n+1];
for(i=0;i<n;i++)
a[i]=r.nextInt(90);
/*System.out.println("Array before sorting");

16
DAA LAB MANUAL

for(i=0;i<n;i++)
System.out.print(a[i]+" ");*/
a[n]=99;
long start=System.nanoTime();
q.sort(a,0,n-1);
long end=System.nanoTime();
/*System.out.println("Sorted array is");
for(i=0;i<n;i++)
System.out.print(a[i]+" ");*/
System.out.println("The time taken by Quick sort is "+(end-start)+"ns");
}
}

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.

import java.util.Random;
import java.util.Scanner;
public class mergesort
{
void merge( int[] a,int low, int mid,int high)
{
int i=low;
int j=mid+1;
int k=low;
int[] result=new int[high+1];
while(i<=mid&&j<=high)

17
DAA LAB MANUAL

{
if(a[i]<a[j])
{
result[k]=a[i];
i++;
k++;
}
else
{
result[k]=a[j];
j++;
k++;
}
}
while(i<=mid)
result[k++]=a[i++];
while(j<=high)
result[k++]=a[j++];
for(int m=low;m<=high;m++)
a[m]=result[m];
}
void sort( int[] a,int low,int high)
{
if(low<high)
{
int mid=(low+high)/2;
sort(a,low,mid);
sort(a,mid+1,high);
merge(a,low,mid,high);
}
}

18
DAA LAB MANUAL

public static void main(String[] args)

{

int i;
System.out.println("Enter the array size");
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();
int[] a= new int[n];
Random generator=new Random();
for( i=0;i<n;i++)
a[i]=generator.nextInt(200);
/*System.out.println("Array before sorting");
for( i=0;i<n;i++)
System.out.print(a[i]+" ");*/
mergesort m=new mergesort();
long startTime=System.nanoTime();
m.sort(a,0,n-1);
long stopTime=System.nanoTime();
long elapseTime=(stopTime-startTime);
System.out.println("Time taken to sort array is: "+elapseTime+" ns");
/*System.out.println("Sorted array is");
for(i=0;i<n;i++)
System.out.print(a[i]+ " "); */
}
}

6.b. Implement in Java, the 0/1 Knapsack problem using Greedy method.

import java.util.Scanner;
class knapsack
{

19
DAA LAB MANUAL

public void k(int n,int w[],int p[],int m)

{
double x[]=new double[n];
double profit=0;
int i;
double u=m;

for( i=0;i<n;i++)
{
if(w[i]>u)
continue;
else
{
x[i]=1;
profit=profit+p[i];
u=u-w[i];
}
}
System.out.println("soulution vector");
for(i=0;i<n;i++)
System.out.println(x[i]);
System.out.println("selected items");
for( i=0;i<n;i++)
{
if(x[i]==1)
System.out.println(i+1);
}
System.out.println("profit:"+profit);
}

public static void main(String[] args)

20
DAA LAB MANUAL

Scanner scan = new Scanner(System.in);

knapsack ks = new knapsack();
System.out.println("Enter number of items:");
int n = scan.nextInt();
int[] w = new int[n];
int[] p = new int[n];
double[] ratio=new double[n];
System.out.println("\nEnter weights of the items");
for (int i=0; i<n; i++)
w[i] = scan.nextInt();
System.out.println("\nEnter profits of the items");
for (int i=0; i<n; i++)
p[i] = scan.nextInt();
System.out.println("\nEnter knapsack capacity:");
int m = scan.nextInt();
for (int i=0;i<n; i++)
ratio[i]=(double)p[i]/w[i];
double temp2;
int temp1;
for (int i=0; i<n-1; i++)
{
for (int j=i+1;j<n; j++)
{
if(ratio[i]<ratio[j])
{
temp2=ratio[j];
ratio[j]=ratio[i];
ratio[i]=temp2;

21
DAA LAB MANUAL

temp1=w[j];
w[j]=w[i];
w[i]=temp1;

temp1=p[j];
p[j]=p[i];
p[i]=temp1;
}
}
}
ks.k(n,w, p, m);
}
}

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.

import java.util.Scanner;
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=0;v<n;v++)
{
d[v]=99;
p[v]=-1;
}

22
DAA LAB MANUAL

d[s]=0;
for(i=0;i<n;i++)
{
min=99;
for(j=0;j<n;j++)
{
if(d[j]<min&& visited[j]==0)
{
min=d[j];
u=j;
}
}
visited[u]=1;
for(v=0;v<n;v++)
{
if((d[u]+a[u][v]<d[v])&&visited[v]==0)
{
d[v]=d[u]+a[u][v];
p[v]=u;
}
}
}
}
void path(int v,int s)
{
if(p[v]!=-1)
path(p[v],s);
if(v!=s)
System.out.print("->"+v+" ");
}

23
DAA LAB MANUAL

void display(int s,int n)

{
int i;
for(i=0;i<n;i++)
{
if(i!=s)
{
System.out.print(s+" ");
path(i,s);
System.out.print("="+d[i]+" ");
System.out.println();
}
}
}
public static void main(String[] args)
{
int a[][]=new int[10][10];
int i,j,n,s;
System.out.println("enter the number of vertices");
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
System.out.println("enter the weighted matrix");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=sc.nextInt();
System.out.println("enter the source vertex");
s=sc.nextInt();
Dijkstra tr=new Dijkstra();
tr.dijk(a,s,n);
System.out.println("the shortest path between source"+s+"to remaining vertices are");
tr.display(s,n);

24
DAA LAB MANUAL

}
}

8. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.
Implement the program in Java language.

import java.util.Scanner;
public class kruskal
{
int parent[]=new int[10];
int find(int p)
{
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 krkl(int[][]a, int n)
{
int u=0,v=0,min,k=0,i,j,sum=0;
while(k<n-1)
{
min=99;
for(i=0;i<n;i++)
for(j=0;j<n;j++)

25
DAA LAB MANUAL

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);
System.out.println("("+u+","+v+")"+"="+a[u][v]);
sum=sum+a[u][v];
k++;
}
a[u][v]=a[v][u]=99;
}
System.out.println("The cost of minimum spanning tree = "+sum);
}
public static void main(String[] args)
{
int i,j;
System.out.println("Enter the number of vertices of the graph");
Scanner sc=new Scanner(System.in);
int n;
n=sc.nextInt();
int a[][]=new int[n][n];
System.out.println("Enter the wieghted matrix");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=sc.nextInt();

26
DAA LAB MANUAL

kruskal k=new kruskal();

k.krkl(a,n);
}
}

9. Find Minimum Cost Spanning Tree of a given undirected graph using Prim's algorithm.
Implement the program in Java language.

import java.io.*;
import java.util.Scanner;
public class prims
{
public static void main(String[] args)
{
int w[][]=new int[10][10];
int n,i,j,s,k=0;
int min;
int sum=0;
int u=0;
int v=0;
int flag=0;
System.out.println("Enter the number of vertices");
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int sol[]=new int[n];
System.out.println("Enter the weighted graph");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
w[i][j]=sc.nextInt();
System.out.println("Enter the source vertex");
s=sc.nextInt();

27
DAA LAB MANUAL

sol[s]=1;
k=1;
while (k<=n-1)
{
min=99;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(sol[i]==1&&sol[j]==0)
if(i!=j&&min>w[i][j])
{
min=w[i][j];
u=i;
v=j;
}
sol[v]=1;
sum=sum+min;
k++;
System.out.println(u+"->"+v+"="+min);
}
for(i=0;i<n;i++)
if(sol[i]==0)
flag=1;
if(flag==1)
System.out.println("No spanning tree");
else
System.out.println("The cost of minimum spanning tree is "+sum);
}
}

10.a. Write Java programs to Implement All-Pairs Shortest Paths problem using Floyd's algorithm.

import java.util.*;

28
DAA LAB MANUAL

class Floyd
{
int min(int i,int j)
{
if(i<j)
return i;
else return j;
}
void result(int[][] w,int n)
{
int i,j,k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
w[i][j]=min(w[i][j], w[i][k]+w[k][j]);
System.out.println("The shortest path matrix is");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
System.out.print(w[i][j]+" ");
}
System.out.println();
}
}
public static void main(String[] args) {

int n,i,j;
int a[][]=new int[10][10];
System.out.println("enter the number of vertices");
Scanner sc=new Scanner(System.in);

29
DAA LAB MANUAL

n=sc.nextInt();
System.out.println("Enter the weighted matrix");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=sc.nextInt();
Floyd f=new Floyd();
f.result(a, n);
}
}

30