GCD and LCM

import [Link];
public class gcdno
{
public static void main(String[] args)
{
int x , y , gcd = 1;
Scanner sc=new Scanner([Link]);
x=[Link]();
y=[Link]();
for(int i = 1; i <= x && i <= y; i++)
{
if(x%i==0 && y%i==0)
gcd = i;
}
[Link]("GCD of %d and %d is: %d", x, y, gcd);
}
}
Output:
Fibonacci series

import [Link];

public class Fibbo{

public static int fiboRecur(int n)
{
if(n == 0)
{
return 0;
}
if(n == 1 || n == 2)
{
return 1;
}
return fiboRecur(n-2) + fiboRecur(n-1);
}
public static void main(String args[])
{
Scanner sc=new Scanner([Link]);

int N;
N=[Link]();

[Link]("Fibonacci Series of "+N+" numbers: ");

for(int i = 0; i < N; i++)
{
[Link](fiboRecur(i) +" ");
}
}
}
Output:
Selection Sort
import [Link];
public class SSort
{
public static void selectionSort(int[] arr,int n){
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (arr[i] > arr[j])
{
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}

}
}

public static void main(String a[])

{
int n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements you want to store: ");
n=[Link]();
int[] array = new int[10];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
array[i]=[Link]();
}
[Link]("Before Selection Sort");
for(int i=0; i<n; i++) {
[Link](array[i]+" ");
}
[Link]();
selectionSort(array,n);
[Link]("After Selection Sort");
for(int i=0; i<n; i++)
{
[Link](array[i]+" ");
}
}
}
Output:
Bubble Sort
import [Link];
public class BSort {
public static void bubbleSort(int[] arr,int n){
for (int i = 0; i < n - 1; i++)
{
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}

}
}

public static void main(String a[])

{
int n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements you want to store: ");

n=[Link]();

int[] array = new int[10];

[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{

array[i]=[Link]();
}

[Link]("Before Bubble Sort");

for(int i=0; i<n; i++) {
[Link](array[i]+" ");
}
[Link]();

bubbleSort(array,n);

[Link]("After Bubble Sort");

for(int i=0; i<n; i++) {
[Link](array[i]+" ");
}
}
}
Output:
Linear Search
import [Link];
public class LinearSearch
{
public static int linearSearch(int[] arr, int key,int n)
{
for(int i=0;i<n;i++)
{
if(arr[i] == key)
{
return i;
}
}
return -1;
}
public static void main(String a[])
{
int n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements you want to store: ");
n=[Link]();
int[] array = new int[10];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
array[i]=[Link]();
}

[Link]("Enter the element to search: ");

int key =[Link]();
int index= linearSearch(array, key,n);
if (index>=0)
[Link](key+" is found at location: "+(index+1));
else
[Link](key+" is not found ");
}
}
Output:
Binary Search
import [Link];
class BinarySearch
{
public static void binarySearch(int arr[], int first, int last, int key)
{
int mid = (first + last)/2;
while( first <= last )
{
if ( arr[mid] < key )
{
first = mid + 1;
}
else if ( arr[mid] == key )
{
[Link]("Element is found at location: " + (mid+1));
break;
}
else
{
last = mid - 1;
}
mid = (first + last)/2;
}
if ( first > last )
{
[Link]("Element is not found!");
}
}
public static void main(String args[]){
int n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements you want to store: ");
n=[Link]();
int[] array = new int[10];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
array[i]=[Link]();
}

[Link]("Enter the element to search: ");

int key =[Link]();

binarySearch(array,0,n-1,key);
}
}
Output:
Stack operations (Push(), Pop(), and Display()) using arrays.

import [Link];
public class stackoper
{
int max=5;
int s[]=new int[max];
int top=-1;
void push(int ele)
{
if(top>=max-1)
[Link]("stack overflow");
else
s[++top]=ele;
}
int pop()
{
int z=0;
if(top==-1)
[Link]("stack underflow");
else
z=s[top--];
return z;
}
void display()
{
if(top==-1)
[Link]("stack empty");
else
{
for(int i=top;i>-1;i--)
[Link](s[i]+" ");
}
}

public static void main(String args[])

{
int q=1;
stackoper m = new stackoper();
[Link]("program to perform stack operations");
Scanner sc=new Scanner([Link]);
while(q!=0)
{
[Link]("1. Push [Link] 3. Display [Link]");
[Link]("Enter your choice");
int ch=[Link]();
switch(ch)
{
case 1:
[Link]("enter the element to be pushed");
 int ele=[Link]();
[Link](ele);
break;
case 2:
int popele;
popele=[Link]();
[Link]("the poped element is");
[Link](popele+" ");
break;
case 3:
[Link]("elements in the stack are");
[Link]();
break;
case 4:
q=0;
}
}
}
}
Output:
Binomial coefficient
import [Link];
class BCE {

static int binomialCoeff(int n, int k)

{

if (k > n)
return 0;
if (k == 0 || k == n)
return 1;

return binomialCoeff(n - 1, k - 1)
+ binomialCoeff(n - 1, k);
}

public static void main(String[] args)

{
int n,k ;
Scanner sc=new Scanner([Link]);
[Link]("Enter n value ");
n=[Link]();
[Link]("Enter k value ");
k=[Link]();
[Link]("BinomialCoeff of C(%d, %d) is\n",n,k);

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

{
for (int j=0; j<=i && j<=k;j++)
[Link](" %d \t",binomialCoeff(i, j));
[Link]("\n");
}
}}
Output:
Warshall’s Algorithm

import [Link];
class Warshall
{
public static void Trans_Clos(int p[][],int n)
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(j=1;j<=n;j++)
{
for(i=1;i<=n;i++)
{
if((p[i][j]==0) && (p[i][k]==1) && (p[k][j]==1))
{ p[i][j]=1;}
}
}
} }
public static void main(String args[])
{int[][] array = new int[10][10];
int i,j,n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of nodes: ");
n=[Link]();
[Link]("Enter the adjacency matrix: ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
array[i][j]=[Link]();
}
}
Trans_Clos(array,n);
[Link]("Transitive Closure : ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
[Link](" %d \t",array[i][j]);
}
[Link]("\n");
}
}
}
Output:
Floyd’s Algorithm:
import [Link];
public class fld
{
public static void Dis_mat(int p[][],int n)
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(j=1;j<=n;j++)
{
for(i=1;i<=n;i++)
{
if( (p[i][k]+p[k][j]) < p[i][j] )
{
p[i][j]=p[i][k]+p[k][j];
} }
} }
}

public static void main(String args[])

{int[][] array = new int[10][10];
int i,j,n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of nodes: ");
n=[Link]();
[Link]("Enter the weigthed matrix: ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
array[i][j]=[Link]();
}
}
Dis_mat(array,n);
[Link]("Distance matrix : ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
[Link](" %d \t",array[i][j]);
}
[Link]("\n");
}
}
}
Output:
Knapsack Problem
import [Link];
public class DPknapsack
{
static int max(int a, int b)
{
return (a > b)? a : b;
}
static int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int [][]K = new int[n+1][W+1];
int []item = new int[n];
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)

K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);

else
K[i][w] = K[i-1][w];
}}
[Link]("KnapSack Problem Dynamic Programming ");
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
[Link](" %d \t",K[i][w]);}
[Link]("\n");}

return K[n][W];
}
public static void main(String args[])
{
Scanner sc = new Scanner([Link]);
[Link]("Enter the number of items: ");
int n = [Link]();
[Link]("Enter the items weights: ");
int []wt = new int[n];
for(int i=0; i<n; i++)
wt[i] = [Link]();
[Link]("Enter the items values: ");
int []val = new int[n];
for(int i=0; i<n; i++)
val[i] = [Link]();
 [Link]("Enter the maximum capacity: ");
int W = [Link]();
[Link]("The max value in knapsack is: " + knapSack(W, wt, val, n));
[Link]();
}
}
Output:
Prim’s Algorithm
import [Link];
public class Prim
{
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,v=0;
int flag=0;
int sol[]=new int[10];
[Link]("Enter the number of vertices");
Scanner sc=new Scanner([Link]);
n=[Link]();
for(i=1;i<=n;i++)
sol[i]=0;
[Link]("Enter the weighted graph");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
w[i][j]=[Link]();
[Link]("Enter the source vertex");
s=[Link]();
sol[s]=1;
k=1;
while (k<=n-1)
{
min=99;
for(i=1;i<=n;i++)
for(j=1;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++;
[Link](u+"->"+v+"="+min);
}
for(i=1;i<=n;i++)
if(sol[i]==0)
flag=1;
if(flag==1)
[Link]("No spanning tree");
else
 [Link]("The cost of minimum spanning tree is"+sum);
[Link]();
}
}
Output:
Kruskal’s Algorithm

import [Link];
public class kruskal
{
int parent[]=new int[10];
int find(int m)
{
int p=m;
while(parent[p]!=0)
p=parent[p];
return p;
}

void union(int i,int j)

{
if(i<j)
parent[i]=j;
else
parent[j]=i;
}

void 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=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][j]<min&&i!=j)
{
min=a[i][j];
u=i;
v=j;
}
i=find(u);
j=find(v);
if(i!=j)
{
union(i,j);
[Link]("("+u+","+v+")"+"="+a[u][v]);
sum=sum+a[u][v];
k++;
}
a[u][v]=a[v][u]=99;
}
[Link]("The cost of minimum spanning tree = "+sum);
}
 public static void main(String[] args)
{
int a[][]=new int[10][10];
int i,j;
[Link]("Enter the number of vertices of the graph");
Scanner sc=new Scanner([Link]);
int n;
n=[Link]();

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

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=[Link]();
kruskal k=new kruskal();
[Link](a,n);
[Link]();
}
}
Output:
Topological Ordering
import [Link];
class Tsort
{
public static void findindegree(int a[][],int indegree[],int n)
{
int i,j,sum;
for(j=1;j<=n;j++)
{
sum=0;
for(i=1;i<=n;i++)
{
sum=sum+a[i][j];
}
indegree[j]=sum;
}
}
public static void topological(int p[][],int n)
{
int[] t = new int[10];
int[] indegree = new int[10];
int[] s = new int[10];
int k,top,i,u,v;
k=1;
top=-1;
findindegree(p,indegree,n);
for(i=1;i<=n;i++)
{
if(indegree[i]==0)
{
s[++top]=i;
}
}
while(top!=-1)
{
u=s[top--];
t[k++]=u;
for(v=1;v<=n;v++)
{
if(p[u][v]==1)
{
indegree[v]--;
if(indegree[v]==0)
{
s[++top]=v;
}}}}
[Link]("Topological sequence is");
for(i=1;i<=n;i++)
[Link]("%d \t",t[i]);
}

public static void main(String args[])

{
int[][] array = new int[10][10];
int i,j,n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of nodes: ");
n=[Link]();
[Link]("Enter the adjacency matrix: ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
array[i][j]=[Link]();
}
}
[Link]("\nThe adjacency matirx is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
[Link]("%d \t",array[i][j]);
}
[Link]("\n");
}
topological(array,n);
}
}
Output:
Breadth First Search
import [Link];
class bfs
{
public static void BFS(int a[][],int source,int visited[],int n)
{
int[] queue = new int[10];
int f,r,u,v;
f=0;
r=-1;
queue[++r]=source;
while(f<=r)
{
u=queue[f++];
for(v=1;v<=n;v++)
{
if(a[u][v]==1 && visited[v]==0)
{
queue[++r]=v;
visited[v]=1;
}
}
}
}
public static void main(String args[])
{
int[][] array = new int[10][10];
int n,i,j,source;
int[] visited = new int[10];
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of nodes: ");
n=[Link]();
[Link]("Enter the adjacency matrix: ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
array[i][j]=[Link]();
}
}
for(i=1;i<=n;i++)
visited[i]=0;
[Link]("Enter source node: ");
source=[Link]();
visited[source]=1;
[Link]("\nThe adjacency matirx is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
[Link]("%d \t",array[i][j]);
}
[Link]("\n");
}
BFS(array,source,visited,n);
for(i=1;i<=n;i++)
{
if(visited[i]!=0)
[Link]("Node %d is reachable \n ",i);
else
[Link]("Node %d is not reachable \n ",i);
}
}}
Output:
Depth First Search

import [Link];
class dfs
{
public static void DFS(int a[][],int source,int visited[],int n)
{
int v; visited[source]=1;
for(v=1;v<=n;v++)
{
if(a[source][v]==1 && visited[v]==0)
DFS(a,v,visited,n);
}}
public static void main(String args[])
{
int[][] array = new int[10][10];
int n,i,j,source,f=0;
int[] visited = new int[10];
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of nodes: ");
n=[Link]();
[Link]("Enter the adjacency matrix: ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
array[i][j]=[Link]();
}}
for(i=1;i<=n;i++)
visited[i]=0;
[Link]("Enter source node: ");
source=[Link]();
visited[source]=1;
[Link]("\nThe adjacency matirx is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
[Link]("%d \t",array[i][j]);
}
[Link]("\n");
}
DFS(array,source,visited,n);
for(i=1;i<=n;i++)
{
if(visited[i]==0)
{
[Link]("Graph is not connected \n ");
f=1;
break;
}}
if (f==0)
[Link]("Graph is connected \n ");
}}
Output:
Quick Sort
import [Link];
import [Link];
public class Qsort
{
public static void main(String[] args)
{
int a[]= new int[100000];
Scanner in = new Scanner([Link]);
long start, end;
[Link]("QUICK SORT PROGRAM");
[Link]("Enter the number of elements to be sorted");
int n = [Link]();
Random rand= new Random();
for(int i=0;i<n;i++)
a[i]=[Link](100);
[Link]("Array elements to be sorted are");
for(int i=0; i<n; i++)
[Link](a[i]+" ");
a[n]=999;
start=[Link]();
quicksort(a,0,n-1);
end=[Link]();
[Link]("\nThe sorted elements are");
for(int i=0; i<n; i++)
[Link](a[i]+" ");
[Link]("\nThe time taken to sort is "+(end-start)+"ns");
}
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 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);
}
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:
Merge Sort

import [Link];
import [Link];

public class Msort

{
public static void main(String[] args)
{
int a[]= new int[100000];
Scanner in = new Scanner([Link]);
long start, end;

[Link]("MERGE SORT PROGRAM");

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

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

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

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

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

}

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:
Subset

import [Link];
import static [Link];
public class subset
{
void subset(int num,int n, int x[])
{
int i;
for(i=1;i<=n;i++)
x[i]=0;
for(i=n;num!=0;i--)
{
x[i]=num%2;
num=num/2;
}
}

public static void main(String[] args)

{
int a[]=new int[10];
int x[]=new int[10];
int n,d,sum,present=0;
int j;
[Link]("enter the number of elements of set");
Scanner sc=new Scanner([Link]);
n=[Link]();
[Link]("enter the elements of set");
for(int i=1;i<=n;i++)
a[i]=[Link]();
[Link]("enter the positive integer sum");
d=[Link]();
if(d>0)
{
for(int i=1;i<=[Link](2,n)-1;i++)
{
subset s=new subset();
[Link](i,n,x);
sum=0;
for(j=1;j<=n;j++)
if(x[j]==1)
sum=sum+a[j];
if(d==sum)
{
[Link]("Subset={ ");
present=1;
for(j=1;j<=n;j++)
if(x[j]==1)
[Link](a[j]+" ");
[Link]("}="+d);
 [Link]();
}
}
}
if(present==0)
[Link]("Solution does not exists");
}
}
Output:
Traveling Salesman Problem

import [Link];
public class TSP
{
public static void main(String[] args)
{
Scanner in = new Scanner([Link]);
int c[][]=new int[10][10], tour[]=new int[10];
int i, j,cost;
[Link]("Enter No. of Cities: ");
int n = [Link]();
if(n==1)
{
[Link]("Path is not possible");
[Link](0);
}
[Link]("Enter the Cost Matrix");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
c[i][j] = [Link]();

for(i=1;i<=n;i++)
tour[i]=i;
cost = tspdp(c, tour, 1, n);
[Link]("\tThe Optimal Tour is = ");
for(i=1;i<=n;i++)
[Link](tour[i]+"->");
[Link]("1");
[Link]("\tMinimum Cost = "+cost);
}

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:
Hamiltonian Cycles

import [Link];
public class Hcycle
{
static int x[] = new int[10];
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
int i,j,x1, x2, edges, n;
int g[][] = new int[10][10];
[Link]("Enter No. of Vertices: ");
n = [Link]();
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
g[i][j] = 0;
x[i]=0;
}
}

[Link]("Enter No. of Edges: ");

edges = [Link]();
for(i=1;i<=edges;i++)
{
[Link]("Enter the Edge"+i+": ");
x1 = [Link]();
x2 = [Link]();
g[x1][x2] = 1;
g[x2][x1] = 1;
}
x[1] = 1;
[Link]("\nHamiltonian Cycle");
hcycle(g,n,2);
}

public static void nextvalue(int g[][],int n,int k)

{
int j;
while(true)
{
x[k] = (x[k] + 1) % (n+1);
if(x[k] == 0)
return;
if(g[x[k-1]][x[k]] == 1)
{
for(j=1;j<=k-1;j++)
{
if(x[j] == x[k] )
 break;
}
if(j == k)
{
if((k<n) || ((k==n) && (g[x[n]][x[1]] == 1)))
return;
}
}
}
}

public static void hcycle(int g[][],int n, int k)

{
int i;
while(true)
{
nextvalue(g,n,k);
if(x[k]== 0)
return;
if(k==n)
{
for(i=1;i<=n;i++)
[Link](x[i]+"-->");
[Link](x[1]+"\n");
}
else
hcycle(g,n,k+1);
}
}
}
Output: