Scribd
Upload
11 views5 pages

Simplified Java Algorithms

The document contains multiple Java implementations of fundamental algorithms including Quick Sort, Merge Sort, Binary Search, Prim's Algorithm, Kruskal's Algorithm, Dijkstra's Algorithm, Matrix Multiplication, Optimal Binary Search Tree (OBST), Longest Common Subsequence (LCS), directed graph traversal (BFS and DFS), and the Floyd-Warshall algorithm for All-Pairs Shortest Paths (APSP). Each algorithm is presented in a separate class with a main method for input and output. The code examples demonstrate the algorithms' functionality and usage with user-provided data.

Uploaded by

sadiazoyasyed
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views5 pages

Simplified Java Algorithms

The document contains multiple Java implementations of fundamental algorithms including Quick Sort, Merge Sort, Binary Search, Prim's Algorithm, Kruskal's Algorithm, Dijkstra's Algorithm, Matrix Multiplication, Optimal Binary Search Tree (OBST), Longest Common Subsequence (LCS), directed graph traversal (BFS and DFS), and the Floyd-Warshall algorithm for All-Pairs Shortest Paths (APSP). Each algorithm is presented in a separate class with a main method for input and output. The code examples demonstrate the algorithms' functionality and usage with user-provided data.

Uploaded by

sadiazoyasyed
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Quick Sort

import [Link].*;
class QuickSort {
static void sort(int a[], int low, int high) {
if (low < high) {
int p = part(a, low, high);
sort(a, low, p - 1);
sort(a, p + 1, high);
}
}
static int part(int a[], int low, int high) {
int pivot = a[high], i = low;
for (int j = low; j < high; j++)
if (a[j] < pivot) { int t=a[i];a[i]=a[j];a[j]=t; i++; }
int t=a[i];a[i]=a[high];a[high]=t;
return i;
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link](); int a[] = new int[n];
for (int i=0;i<n;i++) a[i]=[Link]();
sort(a,0,n-1);
for(int x:a) [Link](x+" ");
}
}

Merge Sort
import [Link].*;
class MergeSort {
static void sort(int a[], int l, int r) {
if (l >= r) return;
int m = (l + r)/2;
sort(a, l, m); sort(a, m+1, r);
merge(a, l, m, r);
}
static void merge(int a[], int l, int m, int r) {
int i=l,j=m+1; List<Integer> t=new ArrayList<>();
while(i<=m && j<=r) [Link](a[i]<=a[j]?a[i++]:a[j++]);
while(i<=m) [Link](a[i++]);
while(j<=r) [Link](a[j++]);
for(int k=0;k<[Link]();k++) a[l+k]=[Link](k);
}
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
int n=[Link](); int a[]=new int[n];
for(int i=0;i<n;i++) a[i]=[Link]();
sort(a,0,n-1);
for(int x:a) [Link](x+" ");
}
}

Binary Search
import [Link].*;
class BinarySearch {
static int search(int a[], int key){
int l=0,r=[Link]-1;
while(l<=r){
int m=(l+r)/2;
if(a[m]==key) return m;
if(a[m]<key) l=m+1; else r=m-1;
}
return -1;
}
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
int n=[Link](); int a[]=new int[n];
for(int i=0;i<n;i++) a[i]=[Link]();
int k=[Link]();
[Link](search(a,k));
}
}

Prim's Algorithm
import [Link].*;
class Prims {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int g[][] = new int[n][n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]=[Link]();
int key[]=new int[n], p[]=new int[n];
boolean mst[]=new boolean[n];
[Link](key,999999);
key[0]=0; p[0]=-1;
for(int c=0;c<n-1;c++){
int u=-1,min=999999;
for(int i=0;i<n;i++)
if(!mst[i]&&key[i]<min){min=key[i];u=i;}
mst[u]=true;
for(int v=0;v<n;v++)
if(g[u][v]!=0 && !mst[v] && g[u][v]<key[v]){
key[v]=g[u][v]; p[v]=u;
}
}
for(int i=1;i<n;i++)
[Link](p[i]+" - "+i+" : "+g[i][p[i]]);
}
}

Kruskal's Algorithm
import [Link].*;
class Kruskal {
static int find(int p[], int x){return p[x]==x?x:(p[x]=find(p,p[x]));}
static void union(int p[], int a, int b){p[find(p,a)] = find(p,b);}
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
int n=[Link](), e=[Link]();
int p[]=new int[n]; for(int i=0;i<n;i++) p[i]=i;
int edges[][]=new int[e][3];
for(int i=0;i<e;i++)
for(int j=0;j<3;j++) edges[i][j]=[Link]();
[Link](edges,[Link](x->x[2]));
for(int[] ed:edges)
if(find(p,ed[0])!=find(p,ed[1])){
[Link](ed[0]+" - "+ed[1]+" : "+ed[2]);
union(p,ed[0],ed[1]);
}
}
}

Dijkstra's Algorithm
import [Link].*;
class Dijkstra {
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
int n=[Link]();
int g[][]=new int[n][n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) g[i][j]=[Link]();
int s=[Link]();
int d[]=new int[n]; boolean vis[]=new boolean[n];
[Link](d,999999); d[s]=0;
for(int c=0;c<n-1;c++){
int u=-1,min=999999;
for(int i=0;i<n;i++)
if(!vis[i]&&d[i]<min){min=d[i];u=i;}
vis[u]=true;
for(int v=0;v<n;v++)
if(g[u][v]!=0 && !vis[v] && d[u]+g[u][v]<d[v])
d[v]=d[u]+g[u][v];
}
for(int i=0;i<n;i++)
[Link](s+" -> "+i+" = "+d[i]);
}
}

Matrix Multiplication
import [Link].*;
class MatrixMultiply {
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
int r1=[Link](), c1=[Link]();
int A[][]=new int[r1][c1];
for(int i=0;i<r1;i++)
for(int j=0;j<c1;j++) A[i][j]=[Link]();
int r2=[Link](), c2=[Link]();
int B[][]=new int[r2][c2];
for(int i=0;i<r2;i++)
for(int j=0;j<c2;j++) B[i][j]=[Link]();
if(c1!=r2){[Link]("Not possible");return;}
int C[][]=new int[r1][c2];
for(int i=0;i<r1;i++)
for(int j=0;j<c2;j++)
for(int k=0;k<c1;k++)
C[i][j]+=A[i][k]*B[k][j];
for(int i=0;i<r1;i++){
for(int j=0;j<c2;j++) [Link](C[i][j]+" ");
[Link]();
}
}
}

OBST
import [Link].*;
class OBST {
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
int n=[Link]();
int k[]=new int[n], f[]=new int[n];
for(int i=0;i<n;i++) k[i]=[Link]();
for(int i=0;i<n;i++) f[i]=[Link]();
int dp[][]=new int[n][n], pre[]=new int[n+1];
for(int i=0;i<n;i++) pre[i+1]=pre[i]+f[i];
for(int g=0;g<n;g++)
for(int i=0,j=g;j<n;i++,j++){
if(g==0) dp[i][j]=f[i];
else{
dp[i][j]=999999;
int sum=pre[j+1]-pre[i];
for(int r=i;r<=j;r++){
int cost=(r>i?dp[i][r-1]:0)+(r<j?dp[r+1][j]:0)+sum;
dp[i][j]=[Link](dp[i][j],cost);
}
}
}
[Link](dp[0][n-1]);
}
}
LCS
import [Link].*;
class LCS {
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
String a=[Link](), b=[Link]();
int n=[Link](), m=[Link]();
int dp[][]=new int[n+1][m+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=([Link](i-1)==[Link](j-1))?
dp[i-1][j-1]+1:[Link](dp[i-1][j],dp[i][j-1]);
[Link](dp[n][m]);
}
}

Digraph
import [Link].*;
class Digraph {
static void bfs(List<List<Integer>> g, int s){
boolean v[]=new boolean[[Link]()];
Queue<Integer> q=new LinkedList<>();
[Link](s); v[s]=true;
while(![Link]()){
int u=[Link](); [Link](u+" ");
for(int x:[Link](u))
if(!v[x]){v[x]=true; [Link](x);}
}
}
static void dfs(List<List<Integer>> g,int u,boolean v[]){
v[u]=true; [Link](u+" ");
for(int x:[Link](u)) if(!v[x]) dfs(g,x,v);
}
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
int n=[Link](), e=[Link]();
List<List<Integer>> g=new ArrayList<>();
for(int i=0;i<n;i++) [Link](new ArrayList<>());
for(int i=0;i<e;i++) [Link]([Link]()).add([Link]());
int s=[Link]();
bfs(g,s); [Link]();
dfs(g,s,new boolean[n]);
}
}

APSP (Floyd-Warshall)
import [Link].*;
class APSP {
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
int n=[Link](), INF=999999;
int d[][]=new int[n][n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
d[i][j]=[Link]();
if(d[i][j]==-1) d[i][j]=INF;
if(i==j) d[i][j]=0;
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=[Link](d[i][j],d[i][k]+d[k][j]);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
[Link]((d[i][j]>=INF?-1:d[i][j])+" ");
[Link]();
}
}
}

You might also like