1.
Java program to print Hello World
public class Hello_DAA {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Welcome to DAA in 4th Sem!!!");
2. Java program to print Hello World 'n' times
import java.util.Scanner;
public class Hello_DAA_2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Enter n: ");
Scanner sc= new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++)
System.out.println("Welcome to DAA in 4th Sem!!!");
3. Java program to add 'n' numbers in an array and find its time complexity
import java.util.Scanner;
public class AddNArr {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Enter n: ");
Scanner sc= new Scanner(System.in);
int n=sc.nextInt();
int sum=0;
int[] arr = new int[n];
System.out.print("Enter array integers: ");
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
long st=System.nanoTime();
add(arr,n);
long end=System.nanoTime();
System.out.println("Time taaken: "+(end-st)+" ns");
}
public static void add(int arr[],int n)
{
int sum=0;
for(int i=0;i<n;i++)
sum=sum+arr[i];
System.out.println("Sum of "+n+" numbers= "+sum);
4. Java program to implement Linear Search concept and find its time complexity
import java.util.Scanner;
public class LinearSearch {
public static int search(int arr[],int n,int key,int i)
{
for(i=0;i<n;i++)
{
if(key==arr[i])
return i;
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int key,i=0,n;
Scanner sc= new Scanner(System.in);
System.out.println("Enter n: ");
n=sc.nextInt();
int arr[]=new int[n];
System.out.println("Enter array: ");
for(i=0;i<n;i++)
arr[i]=sc.nextInt();
System.out.println("Enter key: ");
key=sc.nextInt();
long start= System.nanoTime();
int result=search(arr,n,key,i);
long end=System.nanoTime();
if(result==-1)
System.out.println("Element not found");
else
System.out.println("Element found");
System.out.println("Time taken to search: "+(end-start));
}
}
5. Java program to implement Binary Search concept and find its time complexity
import java.util.Scanner;
public class BinarySearch {
public static int search(int arr[],int n,int key)
{
int b=0,e=n-1,m,i=0;
while(b<=e)
{
m=(b+e)/2;
if(arr[m]==key)
return m;
else if(key<arr[m])
e=m-1;
else
b=m+1;
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int key,i=0,n;
Scanner sc= new Scanner(System.in);
System.out.println("Enter n: ");
n=sc.nextInt();
int arr[]=new int[n];
System.out.println("Enter array: ");
for(i=0;i<n;i++)
arr[i]=sc.nextInt();
System.out.println("Enter key: ");
key=sc.nextInt();
long start= System.nanoTime();
int res=search(arr,n,key);
long end=System.nanoTime();
if(res==-1)
System.out.println("Key value "+key+" not found");
else
System.out.println("Key value "+key+" found");
System.out.println("Time taken to search: "+(end-start));
}
6. Java program to find maximum element and find its time complexity
import java.util.Scanner;
public class MaxEle {
static void Max(int arr[],int n)
{
int max=arr[0];
for(int i=1;i<n;i++)
{
if(arr[i]>max)
max=arr[i];
}
System.out.println("Maximent element: "+max);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
System.out.println("Enter n: ");
int n=sc.nextInt();
System.out.println("Enter array: ");
int[] arr=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
long st=System.nanoTime();
Max(arr,n);
long end=System.nanoTime();
System.out.println("Time taaken: "+(end-st)+" ns");
}
}
7. Java program to implement Tower of Hanoi concept and find its time complexity
public class TowerOfHanoi {
public static void solveHanoi(int n, char fromRod, char toRod, char auxRod) {
if (n == 1) {
System.out.println("Move disk 1 from rod " + fromRod + " to rod " +
toRod);
return;
}
solveHanoi(n - 1, fromRod, auxRod, toRod);
System.out.println("Move disk " + n + " from rod " + fromRod + " to rod " +
toRod);
solveHanoi(n - 1, auxRod, toRod, fromRod);
}
public static void main(String[] args) {
int n = 3;
long st=System.nanoTime();
solveHanoi(n, 'A', 'C', 'B');
long end=System.nanoTime();
System.out.println("Time taaken: "+(end-st)+" ns");
}
}
8. Java program to implement Selection Sort concept and find its time complexity
import java.util.Scanner;
public class SelectionSort {
public static void selectsort(int arr[],int n,int i,int j)
{
int min;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(arr[j]<arr[min])
min=j;
}
int temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int i,j=0;
System.out.println("Enter n: ");
int n=sc.nextInt();
int arr[]=new int[n];
System.out.println("Enter array: ");
for(i=0;i<n;i++)
arr[i]=sc.nextInt();
long start=System.nanoTime();
selectsort(arr,n,i,j);
long end=System.nanoTime();
System.out.print("Sorted array is: ");
for(i=0;i<n;i++)
System.out.print(arr[i]+" ");
System.out.println("\nTime taken to sort: "+(end-start));
9. Java program to implement Bubble Sort concept and find its time complexity
import java.util.*;
public class BubbleSort {
public static void bubblesort(int arr[],int n,int i,int j)
{
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(arr[j+1]<arr[j])
{
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int i,j=0;
System.out.println("Enter n: ");
int n=sc.nextInt();
int arr[]=new int[n];
System.out.println("Enter array: ");
for(i=0;i<n;i++)
arr[i]=sc.nextInt();
long start=System.nanoTime();
bubblesort(arr,n,i,j);
long end=System.nanoTime();
System.out.print("Sorted array is: ");
for(i=0;i<n;i++)
System.out.print(arr[i]+" ");
System.out.println("\nTime taken to sort: "+(end-start));
}
10. Java program to implement Merge Sort concept and find its time complexity
import java.util.*;
public class MergeSort{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Random rand = new Random();
System.out.print("Enter n : ");
int n = in.nextInt();
int[] a = new int[n];
/*for(int i=0;i<n;i++)
{
a[i] = rand.nextInt(100); //Random Inputs
}*/
System.out.println("Enter array: ");
for(int i=0;i<n;i++)
{
a[i]= in.nextInt(); //User Inputs
}
long start = System.nanoTime();
merge_sort(a,0,n-1);
long end = System.nanoTime();
System.out.print("Sorted array : ");
for(int i = 0 ; i < n ; i++)
System.out.print(a[i] + " ");
System.out.println("\nTime taken to execute: " + (end - start) +
"ns");
}
static void merge_sort(int[] a,int low, int high)
{
if(low < high)
{
int mid = (low + high)/2;
merge_sort(a,low,mid);
merge_sort(a,mid + 1,high);
merge(a,low,mid,high);
}
}
static void merge(int[] a, int low, int mid, int high)
{
int i , j , k ;
int[] b = new int[a.length];
i = low ; j = mid + 1; k = low ;
while(i <= mid && j <= high)
{
if(a[i] < a[j])
b[k] = a[i++];
else
b[k] = a[j++];
k++;
}
while(i <= mid)
{
b[k++] = a[i++];
}
while(j <= high)
{
b[k++] = a[j++];
}
for(int m = low ; m <= high ; m++)
a[m] = b[m];
11. Java program to find Maximum and Minimum element in an array and find its time
complexity
import java.util.*;
public class MinMax {
static class Pair
{
int min;
int max;
}
static Pair getMinMax(int arr[],int n)
{
Pair minmax=new Pair();
int i;
//if there is only 1 element, return it as min and max both
if(n==1)
{
minmax.max=arr[0];
minmax.min=arr[0];
return minmax;
}
// if there are more than 1 element, then initialize min and max
if(arr[0]>arr[1])
{
minmax.max=arr[0];
minmax.min=arr[1];
}
else
{
minmax.max=arr[1];
minmax.min=arr[0];
}
for(i=2;i<n;i++)
{
if(arr[i]>minmax.max)
minmax.max=arr[i];
else if(arr[i]<minmax.min)
minmax.min=arr[i];
}
return minmax;
}
public static void main(String args[])
{
int a[]=new int[100000];
Scanner sc=new Scanner(System.in);
Random rand=new Random();
System.out.println("Enter n: ");
int n=sc.nextInt();
long start,end;
/*for(int i=0;i<n;i++)
{
a[i] = rand.nextInt(100); //Random Inputs
}*/
System.out.println("Enter array: ");
for(int i=0;i<n;i++)
{
a[i]= sc.nextInt(); //User Inputs
}
System.out.println("Array is : ");
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
a[n]=999;
start=System.nanoTime();
Pair minmax=getMinMax(a,n);
end=System.nanoTime();
System.out.println("\nThe Minimum element is "+minmax.min);
System.out.println("The Maximum element is "+minmax.max);
System.out.println("\nTime taken to execute: " + (end -
start) + "ns");
}
12. Java program to find Factorial of a number 'n' and find its time complexity
import java.util.Scanner;
public class Factorial {
static int fact(int n)
{
if(n==0)
return 1;
else
return n*fact(n-1);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int f=1,num;
System.out.println("Enter n: ");
Scanner sc=new Scanner(System.in);
num=sc.nextInt();
long st=System.nanoTime();
f=fact(num);
long end=System.nanoTime();
System.out.println("Factorial of "+num+" is "+f);
System.out.println("Time taken to execute: "+(end-st)+"ns");
13. Java program to find Fibonacci series till a number 'n' and find its time
complexity
import java.util.Scanner;
public class Fibonacci {
static void fib(int n,int a,int b,int c)
{
for(int i=2;i<n;i++)
{
c=a+b;
System.out.print(" "+c);
a=b;
b=c;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a=0,b=1,c=0,n;
Scanner sc=new Scanner(System.in);
System.out.println("Enter n: ");
n=sc.nextInt();
System.out.println("Fibonacci Series: ");
System.out.print(a+" "+b);
long st=System.nanoTime();
fib(n,a,b,c);
long end=System.nanoTime();
System.out.println("\nTime taken to execute: "+(end-st)+"ns");
}
14. Java program to implement Quick Sort concept and find its time complexity
import java.util.*;
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
Random rand=new Random();
System.out.println("Enter n: ");
int n=sc.nextInt();
int a[]=new int[10000];
long start,end;
/*for(int i=0;i<n;i++)
{
a[i] = rand.nextInt(100); //Random Inputs
}*/
System.out.println("Enter array: ");
for(int i=0;i<n;i++)
{
a[i]= sc.nextInt(); //User Inputs
}
System.out.println("Array to be sorted is : ");
for(int i=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("\nSorted array is : ");
for(int i=0;i<n;i++)
System.out.print(a[i]+" ");
System.out.println("\nTime taken to execute: " + (end - start) +
"ns");
}
static void quicksort(int a[],int p,int q)
{
int j;
if(p<q)
{
j=partition(a,p,q);
quicksort(a,p,j-1);
quicksort(a,j+1,q);
}
}
static int partition(int a[],int m,int p)
{
int v,i,j;
v=a[m]; //first element=pivot
i=m;
j=p;
while(i<=j)
{
while(a[i]<=v)
i++;
while(a[j]>v)
j--;
if(i<j)
swap(a,i,j);
}
a[m]=a[j];
a[j]=v;
return j;
}
static void swap(int a[],int i,int j)
{
int p;
p=a[i];
a[i]=a[j];
a[j]=p;
}
15. Java program to implement Topological Sort concept using Source Removal Method
and find time complexity to sort elements
import java.util.*;
public class TopoSort {
public static List<Integer>
toposort(List<List<Integer> > adj,int V)
{
//Vector to store indegree of each vertex
int[] indeg=new int[V];
for(List<Integer> list: adj)
{
for(int vertex: list)
{
indeg[vertex]++;
}
}
//Queue to store vertices with indegree 0
Queue<Integer> q= new LinkedList<>();
for(int i=0;i<V;i++)
{
if(indeg[i]==0)
{
q.add(i);
}
}
List<Integer> result= new ArrayList<>();
while(!q.isEmpty())
{
int node=q.poll();
result.add(node);
//Decrease indegree of adjacent vertices as the current
node is in topological order
for(int adjacent: adj.get(node))
{
indeg[adjacent]--;
//If indegree becomes 0,push it to the queue
if(indeg[adjacent]==0)
q.add(adjacent);
}
}
//Check of cycle
if(result.size()!=V)
{
System.out.println("Graph contains cycle!");
return new ArrayList<>();
}
else
{
System.out.println("Graph does not contain cycle!");
return result;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int n=5; //Number of nodes
//Edges
List<List<Integer> > edges =
Arrays.asList(Arrays.asList(0,1),Arrays.asList(2,3),Arrays.asList(3,4),Arrays.asLis
t(4,0));
//Arrays.asList(3,2));
//Graph represented as an adjacency List
List<List<Integer> > adj= new ArrayList<>();
for(int i=0;i<n;i++)
adj.add(new ArrayList<>());
//Constructing adjacency list
for(List<Integer> edge: edges)
adj.get(edge.get(0)).add(edge.get(1));
//Performing toposort
System.out.println("Topological sorting of graph: ");
List<Integer> result= toposort(adj,n);
//Displaying result
System.out.println("Result: ");
for(int vertex: result)
System.out.print(vertex+" ");
16. Java program to implement Coin Changing problem using Greedy method and find
its time complexity
import java.util.*;
public class CoinChange {
static int[] reverse(int arr[])
{
int l=0;
int r=arr.length-1;
while(l<r)
{
int temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
l+=1;
r-=1;
}
return arr;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
System.out.println("Enter no of coins: ");
int n=sc.nextInt();
System.out.println("Enter coins: ");
int[] arr=new int[n];
for (int i=0;i<n;i++)
{
System.out.println("Coin "+(i+1)+":");
arr[i]=sc.nextInt();
}
System.out.println("Enter amount: ");
int amt=sc.nextInt();
Arrays.sort(arr);
reverse(arr);
int[] coins =new int[n];
for(int i=0;i<n;i++)
{
coins[i]=amt/arr[i];
amt=amt %arr[i];
System.out.println("Number of "+arr[i]+" coins required is
"+coins[i]);
}
17. Java program to find maximum profit using Knapsack technique(Greedy method)
import java.util.Scanner;
class GreedyKnapsack
{
private int n;
private int m;
private int[] w;
private int[] p;
public GreedyKnapsack(int n,int m,int[] w,int[] p)
{
this.n=n;
this.m=m;
this.w=w;
this.p=p;
}
public void greedy()
{
float sum=0,max; //sum: profit
int i,j=0;
while(m>=0)
{
max=0;
for(i=0;i<n;i++)
{
if(((float)p[i])/((float)w[i])>max)
{
max=((float)p[i])/((float)w[i]);
j=i;
}
}
if(w[j]>m)
{
System.out.println("Quantity of item number
"+(j+1)+" added is "+(float)m/w[j]);
sum=sum+m*max;
m=-1;
}
else
{
System.out.println("Quantity of item number
"+(j+1)+" added fully");
m=m-w[j];
sum=sum+(float)p[j];
p[j]=0;
}
}
System.out.println("Total profit: is "+sum);
}
}
public class Knapsack {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int i,max_qty,m,n;
int w[]=new int[10];
int p[]=new int[10];
System.out.println("Enter no. of items: ");
n=sc.nextInt();
System.out.println("Enter the weights of each items: ");
for(i=0;i<n;i++)
w[i]=sc.nextInt();
System.out.println("Enter the profit of each items: ");
for(i=0;i<n;i++)
p[i]=sc.nextInt();
System.out.println("Enter the knapsack capacity: ");
max_qty=sc.nextInt();
m=max_qty;
GreedyKnapsack gks=new GreedyKnapsack(n,m,w,p);
gks.greedy();
sc.close();
18. Java program to implement Job Sequence problem using Greedy method
import java.util.Arrays;
import java.util.Scanner;
class Job
{
int id,profit,deadline;
public Job(int id,int profit,int deadline)
{
this.id=id;
this.profit=profit;
this.deadline=deadline;
}
}
public class Job_Seq {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
System.out.println("Enter number of jobs: ");
int n=sc.nextInt();
Job[] jobs= new Job[n];
for(int i=0;i<n;i++)
{
System.out.println("Enter profit and deadline for job
"+(i+1));
int profit =sc.nextInt();
int deadline=sc.nextInt();
jobs[i]=new Job(i+1, profit,deadline);
}
Arrays.sort(jobs,(a,b)->b.profit-a.profit);
int maxDeadline=0;
for(Job job: jobs)
{
if(job.deadline> maxDeadline)
maxDeadline = job.deadline;
}
int[] slot = new int[maxDeadline+1];
Arrays.fill(slot, -1);
int totalProfit=0;
int jobCount=0;
for(Job job: jobs)
{
for(int j=job.deadline;j>0;j--)
{
if(slot[j]==-1)
{
slot[j]=job.id;
totalProfit+=job.profit;
jobCount++;
break;
}
}
}
System.out.println("Number of jobs done: "+jobCount);
System.out.println("Total profit: "+totalProfit);
sc.close();
