Views:
These are the AOAD (Analysis of Algorithm and Design) practical codes for the Computer Engineering students of Mumbai University.
1) All Pairs shortest path:
import java.util.*;
class AllPair
{
public static void main(String args[])
{
Scanner s = new Scanner(System.in);
int cm[][],x[][], v, e, k, i ,j;
System.out.println("Enter the number of vertices");
v = s.nextInt();
System.out.println("Enter the number of edges");
e = s.nextInt();
cm = new int[v+1][v+1];
for(i=1; i<=v; i++)
for(j=1; j<=v; j++)
{
System.out.println("Enter the cost of edges" + i + "-" + j);
cm[i][j] = s.nextInt();
}
x = new int[v+1][v+1];
for(i=1; i<=v; i++)
{
for(j=1; j<=v; j++)
{
x[i][j] = cm[i][j];
System.out.print(x[i][j]+"\t");
}
System.out.println();
}
for(k=1; k<=v ; k++)
{
for(i=1; i<=v; i++)
{
for(j=1; j<=v; j++)
{
x[i][j] = Math.min(x[i][j], (x[i][k] + x[k][j]));
}
}
}
System.out.println("The shortest path is");
{
for(i=1; i<=v; i++)
{
for(j=1; j<=v; j++)
{
System.out.print(x[i][j] + "\t");
}
System.out.println();
}
}
}
}
2) Bellman ford:
import java.util.Scanner;
class BMF1
{
int n,adj[][],cost[][],u,v,i,j,k,dist[];
BMF1()
{
Scanner src=new Scanner(System.in);
System.out.println("Enter number of vertices");
n=src.nextInt();
adj=new int[n+1][n+1];
cost=new int[n+1][n+1];
dist=new int[n+1];
System.out.println("Enter adjecency matrix");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
adj[i][j]=src.nextInt();
if(i!=j)
cost[i][j]=32767;
}
for(j=1;j<=n;j++)
if(adj[i][j]==1)
{
System.out.println("Enter cost of path from "+i+" to "+j);
cost[i][j]=src.nextInt();
}
System.out.println("Enter source");
v=src.nextInt();
System.out.println("Enter destination");
u=src.nextInt();
bellman(v,u,cost,adj,n);
}
void bellman(int v,int u,int cost[][],int adj[][],int n )
{
for(i=1;i<=n;i++)
dist[i]=cost[v][i];
for(k=2;k<=n-1;k++)
for(i=1;i<=n;i++)
if(adj[i][u]==1)
if(dist[u]>dist[i]+cost[i][u])
dist[u]=dist[i]+cost[i][u];
System.out.println("Shortest distance from "+v+" to "+u+"="+dist[u]);
}
}
class BMF
{
public static void main(String args[])
{
BMF1 bmf=new BMF1();
}
}
/*Output:
Enter number of vertices
4
Enter adjecency matrix
0 1 1 1
0 0 0 1
0 0 0 1
0 0 0 0
Enter cost of path from 1 to 2
2
Enter cost of path from 1 to 3
3
Enter cost of path from 1 to 4
9
Enter cost of path from 2 to 4
1
Enter cost of path from 3 to 4
-2
Enter source
1
Enter destination
4
Shortest distance from 1 to 4=1
*/
3) Binary search:
class BinarySearch
{
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
System.out.println("Enter the no of integers in array:");
int n= in.nextInt();
System.out.println("Enter the array elements in increasing order:");
int a[]=new int[10];
for(int i=0;i<n;i++)
a[i]=in.nextInt();
System.out.println("Entered array");
for(int i=0;i<n;i++)
System.out.print(" "+a[i]);
System.out.println("\nEnter the element to be searched:");
int x=in.nextInt();
int c=binsearch(a,n,x);
if(c==-1)
System.out.println("Not found");
}
public static int binsearch(int a[],int n,int x)
{
int low=0,high=n-1,mid;
while(low<=high)
{
mid=(low+high)/2;
if(x==a[mid])
{
System.out.println("Element present. Found at position:"+(mid+1));
return(a[mid]);
}
if(x<a[mid])
high=mid-1;
else
low=mid+1;
}
return(-1);
}
}
import java.io.*;
import java.lang.*;
class boyre
{
static int boyreMoore(String T,String P)
{
int n=T.length();
int m=P.length();
int i=m-1;int j=m-1;
do
{
if(P.charAt(j)==T.charAt(i))
{
if(j==0)
return i;
else
{
i--;
j--;
}
}
else
{
i=i+m-Math.min(j,1+(last(T,P,i)));
j=m-1;
}
}
while(i<=n-1);
return -1;
}
static int last(String T,String P,int i)
{
return P.lastIndexOf(T.charAt(i));
}
public static void main(String args[]) throws IOException
{
DataInputStream in=new DataInputStream(System.in);
int n,m,a=0,s,i;
System.out.println("Enter the length of string T and P");
n=Integer.parseInt(in.readLine());
m=Integer.parseInt(in.readLine());
String T,P;
System.out.println("Enter the T and P string");
T=in.readLine();
P=in.readLine();
a=boyreMoore(T,P);
if(a==-1)
{
System.out.println("Match not found");
}
else
{
s=a;
s++;
System.out.println("Match found at"+s);
}
}
}
5) Brute force:
import java.io.*;
class Brute
{
public static void main(String args[])throws IOException
{
String t,p;
DataInputStream in=new DataInputStream(System.in);
System.out.println("Enter main String");
t=in.readLine();
System.out.println("\nEnter sub String");
p=in.readLine();
brutes(t,p);
}
static void brutes(String t,String p)
{
int n=t.length();
int m=p.length();
int i,j;
boolean flag=false;
for(i=0;i<=n-m;i++)
{
j=0;
flag=false;
while(j<m && (t.charAt(i+j)==p.charAt(j)))
{
j=j+1;
flag=true;
}
if(j==m)
System.out.println("\nMatch found at "+i);
}
if(flag==false)
System.out.println("\nNo match found");
}
}
/*
OUTPUT:
Enter main String
abacaabaccabacabaabb
Enter sub String
abacab
Match found at 10
*/
6) Dijkstras:
import java.util.*;
class Dijkastra1
{
int dist[], adj[][],path[],w[][],src,dest, nodeset[],n;
Dijkastra1()
{
Scanner s = new Scanner(System.in);
System.out.println("Enter the number of nodes");
n= s.nextInt();
adj = new int[n+1][n+1];
dist = new int[n+1];
nodeset = new int[n+1];
w = new int[n+1][n+1];
path = new int[n+1];
System.out.println("Enter Adjacency MAtrix");
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
adj[i][j] = s.nextInt();
}
}
final int inf = 32767;
for(int i=1;i<=n;i++)
{
dist[i] = inf;
nodeset[i] = 0;
}
for(int i =1;i<=n; i++)
{
for(int j =1; j<=n; j++)
{
if(adj[i][j]==1)
{
System.out.println("Enter the weight of edge b/w " + i + "and " + j);
w[i][j] =s.nextInt();
}
}
}
System.out.println("Enter the source and destination");
src = s.nextInt();
dest = s.nextInt();
}
void shortest()
{
int dc,mindist,newdist,i;
int current = src;
dist[current] =0;
nodeset[current] = 1;
while(current!= dest)
{
dc = dist[current];
for(i =1;i<=n;i++)
{
if(adj[current][i]==1 && nodeset[i]!=1)
{
newdist = dc + w[current][i];
if(newdist<dist[i])
{
dist[i] = newdist;
path[i] = current;
}
}
}
mindist = 32767;
for(i =1;i<=n;i++)
{
if(nodeset[i]!=1 && dist[i]<mindist)
{
mindist = dist[i];
current = i;
}
}
nodeset[current] = 1;
}
System.out.println("Minimum dist from " + src+ "to" + dest+" = " + dist[dest]);
int x;
i=dest;
String z =" ";
do
{
x=path[i];
z+= String.valueOf(i);
i=x;
}
while(i!=src);
System.out.println("Path:");
z+= String.valueOf(i);
i = z.length() - 1;
for(;i>=0;i--)
System.out.print(z.charAt(i) + " - ");
}
}
class Dijkastra
{
public static void main(String args[])
{
(new Dijkastra1()).shortest();
}
}
Output:
Enter the number of nodes
4
Enter Adjacency MAtrix
0 1 1 1
0 0 0 1
0 0 0 0
0 0 1 0
Enter the weight of edge b/w 1and 2
20
Enter the weight of edge b/w 1and 3
10
Enter the weight of edge b/w 1and 4
30
Enter the weight of edge b/w 2and 4
5
Enter the weight of edge b/w 4and 3
40
Enter the source and destination
1 4
Minimum dist from 1to4 = 25
Path:
1 - 2 - 4
7) Graph colouring:
import java.util.Scanner;
class Graph
{
int adj[][],n,col,x[];
Graph()
{
Scanner src=new Scanner(System.in);
System.out.println("Enter number of vertices ");
n=src.nextInt();
adj=new int[n+1][n+1];
x=new int[n+1];
System.out.println("Enter adjecency matrix");
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
adj[i][j]=src.nextInt();
System.out.println("Enter number of colors");
col=src.nextInt();
}
boolean promising(int k)
{
for(int j=1;j<k;j++)
if(adj[j][k]!=0 && x[j]==x[k])
return false;
return true;
}
void color(int k)
{
x[k]=0;
while(k>0)
{
x[k]++;
while(!promising(k) && x[k]<=col)
x[k]++;
if(x[k]>col)
k--;
else
{
if(k==n)
System.out.println(this);
else
{
k++;
x[k]=0;
}
}
}
}
public String toString()
{
for(int i=1;i<=n;i++)
System.out.print(x[i]+" ");
System.out.println();
return "";
}
}
class GraphColor
{
public static void main(String args[])
{
(new Graph()).color(1);
}
}
/*
Output:
Enter number of vertices
4
Enter adjecency matrix
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0
Enter number of colors
3
1 2 3 1
1 2 3 3
1 3 2 1
1 3 2 2
2 1 3 2
2 1 3 3
2 3 1 1
2 3 1 2
3 1 2 2
3 1 2 3
3 2 1 1
3 2 1 3
*/
8) Knapsack:
import java.util.*;
import java.io.*;
class knapsack
{
public static void main(String args[]) throws IOException
{
Scanner in=new Scanner(System.in);
int n,i;
double max,cp;
System.out.println("Enter the no. of elements");
n=in.nextInt();
double index[]=new double[n];
double p[]=new double [n];
double w[]=new double[n];
System.out.println("Enter the profits:");
for(i=0;i<n;i++)
p[i]=in.nextDouble();
System.out.println("Enter the weights respectively;");
for(i=0;i<n;i++)
w[i]=in.nextDouble();
System.out.println("Enter the total capacity");
cp=in.nextDouble();
max=knapsack(p,w,n,cp,index);
System.out.print("Optimal solution:\n"+max+"\n");
}
static double knapsack(double p[],double w[],int n,double cp,double index[])
{
int i,j;
double t;
for(i=0;i<n-1;i++)
for(j=0;j<n-1;j++)
if((p[j]/w[j])<(p[j+1]/w[j+1]))
{
t=p[j];
p[j]=p[j+1];
p[j+1]=t;
t=w[j];
w[j]=w[j+1];
w[j+1]=t;
}
while(cp>0)
{
for(i=0;i<n&&(cp-w[i])>=0.0;i++)
{
index[i]=1.0;
cp=cp-w[i];
}
if(i<n)
{
index[i]=cp/w[i];
cp=cp-w[i];
}
}
double max=0.0;
for(i=0;i<n;i++)
max= max+ (double)(index[i]*p[i]);
return max;
}
}
/*output:
Enter the no. of elements
4
Enter the profits:
4
16
40
13
Enter the weights respectively;
5
4
6
8
Enter the total capacity
25
Optimal solution:
46.33333333333333
*/
import java.io.*;
class knapsack
{
public static void main(String args[]) throws IOException
{
Scanner in=new Scanner(System.in);
int n,i;
double max,cp;
System.out.println("Enter the no. of elements");
n=in.nextInt();
double index[]=new double[n];
double p[]=new double [n];
double w[]=new double[n];
System.out.println("Enter the profits:");
for(i=0;i<n;i++)
p[i]=in.nextDouble();
System.out.println("Enter the weights respectively;");
for(i=0;i<n;i++)
w[i]=in.nextDouble();
System.out.println("Enter the total capacity");
cp=in.nextDouble();
max=knapsack(p,w,n,cp,index);
System.out.print("Optimal solution:\n"+max+"\n");
}
static double knapsack(double p[],double w[],int n,double cp,double index[])
{
int i,j;
double t;
for(i=0;i<n-1;i++)
for(j=0;j<n-1;j++)
if((p[j]/w[j])<(p[j+1]/w[j+1]))
{
t=p[j];
p[j]=p[j+1];
p[j+1]=t;
t=w[j];
w[j]=w[j+1];
w[j+1]=t;
}
while(cp>0)
{
for(i=0;i<n&&(cp-w[i])>=0.0;i++)
{
index[i]=1.0;
cp=cp-w[i];
}
if(i<n)
{
index[i]=cp/w[i];
cp=cp-w[i];
}
}
double max=0.0;
for(i=0;i<n;i++)
max= max+ (double)(index[i]*p[i]);
return max;
}
}
/*output:
Enter the no. of elements
4
Enter the profits:
4
16
40
13
Enter the weights respectively;
5
4
6
8
Enter the total capacity
25
Optimal solution:
46.33333333333333
*/
9) LCS:
AIM: To implement LCS Algorithm
Roll no:
import java.io.*;
class LCS
{
char b[][]=new char[20][20];
DataInputStream in=new DataInputStream(System.in);
void read()throws IOException
{
String x,y;
System.out.println("Enter first String");
x=in.readLine();
System.out.println("Enter second String");
y=in.readLine();
lcss(x,y);
}
void lcss(String x,String y)
{
int m=x.length();
int n=y.length();
int i,j;
int c[][]=new int[m][n];
for(i=0;i<m;i++)
c[i][0]=0;
for(j=0;j<n;j++)
c[0][j]=0;
for(i=1;i<m;i++)
for(j=1;j<n;j++)
if(x.charAt(i)==y.charAt(j))
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]='d';
}
else
if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]='u';
}
else
{
c[i][j]=c[i][j-1];
b[i][j]='l';
}
prints(b,x,i-1,j-1);
}
void prints(char b[][],String x,int i,int j)
{
if((i==0)&&(j==0))
return;
if(b[i][j]=='d')
{
prints(b,x,i-1,j-1);
System.out.print(x.charAt(i)+" ");
}
else
if(b[i][j]=='u')
prints(b,x,i-1,j);
else
prints(b,x,i,j-1);
}
public static void main(String args[])throws IOException
{
LCS l=new LCS();
l.read();
}
}
OUTPUT:
Enter first String
asdadad
Enter second String
asdddd
s d d d
10) N-queens:
/*Aim:To implement nqueens problem using backtracking*/
import java.io.*;
//import java.lang.*;
import java.util.*;
class nqueens
{ static int x[]=new int[15];
public static void main(String args[])throws IOException
{
DataInputStream in=new DataInputStream(System.in);
int n;
System.out.println("Enter the no. of queens");
n=Integer.parseInt(in.readLine());
Nqueens(1,n);
}
static void Nqueens(int k,int n)
{
int i,j;
for(i=1;i<=n;i++)
{
x[k]=i;
if(place(k))
{
if(k==n)
{
for(j=1;j<=n;j++)
System.out.print(" "+x[j]+" ");
System.out.println(" ");
}
else
Nqueens(k+1,n);
}
}
}
static boolean place(int k)
{
int j;
for(j=1;j<=k-1;j++)
{
if((x[j]==x[k])||((Math.abs(x[j]-x[k]))==(Math.abs(j-k))))
return false;
}
return true;
}
}
/*output:
Enter the no. of queens
4
2 4 1 3
3 1 4 2
Press any key to continue...
*/
11) Quick sort:
import java.io.*;
import java.util.*;
class QuickSort
{
static int partition (int a[], int down, int up)
{
int x=a[down],i=down,j=up,temp;
while(i<j)
{
while ((a[i]<=x)&&(i<j))
i++;
while(a[j]>x)
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
a[down]=a[j];
a[j]=x;
return j;
}
static void quicksort(int a[],int down,int up)
{
int mid;
if(down<up)
{
mid=partition(a,down,up);
quicksort(a,down,mid-1);
quicksort(a,mid+1,up);
}
}
public static void main(String args[]) throws IOException
{
Scanner in=new Scanner(System.in);
int n,i,down,up;
System.out.println("Enter the no. of elements");
n=in.nextInt();
int a[]=new int[n];
System.out.println("Enter the "+n+" elements");
for(i=0;i<n;i++)
a[i]=in.nextInt();
System.out.println("\n\nBefore sorting:\n");
for(i=0;i<n;i++)
System.out.print(a[i]+"\t");
quicksort(a,down=0,up=n-1);
System.out.println("\n\n\nAfter sorting:\n");
for(i=0;i<n;i++)
System.out.print(a[i]+"\t");
}
}
12) Sum of subsets:
import java.io.*;
class SumSub
{
static int x[],w[],n,sumr;
public static void main(String args[])throws IOException
{
DataInputStream in=new DataInputStream (System.in);
System.out.println("Enter no of elements ");
n=Integer.parseInt(in.readLine());
w=new int[n+1];
System.out.println("enter elements");
for(int i=1;i<=n;i++)
w[i]=Integer.parseInt(in.readLine());
x=new int[n+1];
System.out.println("enter sum required");
sumr=Integer.parseInt(in.readLine());
sumofsub(1);
}
static int sum(int k)
{
int s=0,i;
for(i=1;i<=k;i++)
s=s+x[i];
return s;
}
static boolean proper(int k,int i)
{
for(int j=1;j<=k-1;j++)
{
if(x[k]==w[i])
return false;
}
if(sum(k-1)+w[i]>sumr)
return false;
else
return true;
}
static void sumofsub(int k)
{
for(int i=k;i<=n;i++)
{
if(proper(k,i))
{
x[k]=w[i];
if(sum(k)==sumr)
{
for(int j=1;j<=k;j++)
System.out.print(x[j]+" ");
System.out.println();
}
else
sumofsub(k+1);
}
}
}
}
Output:
Enter no of elements
5
enter elements
5
10
13
15
25
enter sum required
30
5 10 15
5 25
15 15
To anonymous: whoever u r... 1st check out ur lenses n den ur english grammar
ReplyDeletehey jitu much appreciate your work but uploading programs in this way seems too untidy..just upload it on google in a zip file dat would be much good
ReplyDeletewell.. i tried it for OS programs... bt d link of google docs get expired after some days... dats y i took dis way...
ReplyDelete