Optimal Storage on Tapes

import java.io.*;
class Store
{
    public static void main (String[] args)throws Exception
        {
            DataInputStream d=new DataInputStream(System.in);
            System.out.println("Enter no. of Programs:");
            int n=Integer.parseInt(d.readLine());
            int[] p=new int[n];
            int[] a=new int[n];
            int i;
            System.out.println("Enter the programs with length:");
            for(i=0;i<=n-1;i++)
            {
                System.out.print("Program"+(i+1)+":");
               p[i]=Integer.parseInt(d.readLine());
               System.out.println();
               a[i]=i+1;
               
            }
            for(i=n-2;i>=0;i--)
            {
                for(int j=0;j<=i;j++)
                {
                if(p[j]>p[j+1])
                {
                    int temp=p[j];
                    p[j]=p[j+1];
                    p[j+1]=temp;
                    int t=a[j];
                    a[j]=a[j+1];
                    a[j+1]=t;
                }
                }
            }
            System.out.println("The Best Ordering is");
           
            for(i=0;i<=n-1;i++)
            {
                System.out.println("Program"+a[i]+":"+p[i]);
            }       
}
}
/*Output:
Enter no. of Programs:
3
Enter the programs with length:
Program1:5

Program2:10

Program3:3

The Best Ordering is
Program3:3
Program1:5
Program2:10

Process completed.
*/

Single Source shortest path Usin BellmanFord

import java.io.*;

class  Graph

{
 BufferedReader Bobj= new BufferedReader(new InputStreamReader(System.in));

 int g[][],v,e,d[],p[],visited[];

void Creategraph()throws IOException

       {int a,b,w;
   
     System.out.print("ENTER THE NO OF VETEX=");
   
     v=Integer.parseInt(Bobj.readLine());
   
     System.out.print("ENTER THE NO OF EDGES=");
   
     e=Integer.parseInt(Bobj.readLine());
   
     g=new int[v+1][v+1];
   
     for(int i=1;i<=v;i++)
   
        for(int j=1;j<=v;j++)
       
          g[i][j]=0;
       
     for(int i=1;i<=e;i++)
   
     {System.out.println("ENTER THE EDGE INFORMATION\n");
     
      System.out.print("ENTER THE SORCE VERTEX=");
     
      a=Integer.parseInt(Bobj.readLine());
     
      System.out.print("ENTER THE DESTINATION VERTEX=");
     
      b=Integer.parseInt(Bobj.readLine());
     
      System.out.print("ENTER THE WEIGTH OF EDGE =");
     
      w=Integer.parseInt(Bobj.readLine());
     
      g[a][b]=g[b][a]=w;
      }
   
}

void Callbellmanford()throws IOException

{

 d=new int[v+1];

 p=new int[v+1];

 visited=new int[v+1];

 for(int i=1;i<=v;i++)

   {
  
     p[i]=0;
   
     visited[i]=0;
   
     d[i]=32767;
   }

  bellmanford();
  
}

void bellmanford()throws IOException

{

  BufferedReader Bobj= new BufferedReader(new InputStreamReader(System.in));
  
  int dc,current,mincost=0,source,dest,c;

  System.out.print("\n\n\n\n\n\n\nENTER THE SOURCE VERTEX=");
 
  source=Integer.parseInt(Bobj.readLine());
 
  System.out.print("ENTER THE DESTINATION VERTEX=");
 
  dest=Integer.parseInt(Bobj.readLine());
 
 
 current=source;

 visited[current]=1;

 d[current]=0;



 dc=dest;


 while (current!=dest)

 {

   for(int i=1;i<=v;i++)
  
   {
     if(g[current][i]!=0 && visited[i]!=1)
   
      if (d[i]>g[current][i]+d[current])
      
         {  d[i]=g[current][i]+d[current];
         
          p[i]=current;
         }
 
   }

     for(int i=1;i<=v;i++)

    //mincost+=d[i];

System.out.println("MINIMUM COST="+d[i]);System.out.println();




  
   int min=32767;
  
   for(int i=1;i<=v;i++)
  
   { if (visited[i]!=1 && d[i]
   
     {
      min=d[i];
     
      current=i;
     
     }
   }
  
   visited[current]=1;
  
   //c++;
  
  
  
 }

 System.out.println("******** GRAPH *********");


System.out.println("MINIMUM COST="+d[dest]);
 
}

}

class Bellman
{

 public static void main(String args[])throws IOException

 {
  Graph g=new Graph();
 
  g.Creategraph();
 
  g.Callbellmanford();
 
 }

}
/*Output:
ENTER THE NO OF VETEX=7
ENTER THE NO OF EDGES=10
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=1
ENTER THE DESTINATION VERTEX=2
ENTER THE WEIGTH OF EDGE =6
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=1
ENTER THE DESTINATION VERTEX=3
ENTER THE WEIGTH OF EDGE =5
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=1
ENTER THE DESTINATION VERTEX=4
ENTER THE WEIGTH OF EDGE =5
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=4
ENTER THE DESTINATION VERTEX=3
ENTER THE WEIGTH OF EDGE =-2
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=3
ENTER THE DESTINATION VERTEX=2
ENTER THE WEIGTH OF EDGE =-2
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=2
ENTER THE DESTINATION VERTEX=5
ENTER THE WEIGTH OF EDGE =-1
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=3
ENTER THE DESTINATION VERTEX=5
ENTER THE WEIGTH OF EDGE =1
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=4
ENTER THE DESTINATION VERTEX=6
ENTER THE WEIGTH OF EDGE =-1
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=6
ENTER THE DESTINATION VERTEX=7
ENTER THE WEIGTH OF EDGE =3
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=5
ENTER THE DESTINATION VERTEX=7
ENTER THE WEIGTH OF EDGE =3







ENTER THE SOURCE VERTEX=1
ENTER THE DESTINATION VERTEX=7
MINIMUM COST=0
MINIMUM COST=6
MINIMUM COST=5
MINIMUM COST=5
MINIMUM COST=32767
MINIMUM COST=32767
MINIMUM COST=32767

MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=5
MINIMUM COST=3
MINIMUM COST=6
MINIMUM COST=32767
MINIMUM COST=32767

MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=5
MINIMUM COST=3
MINIMUM COST=2
MINIMUM COST=32767
MINIMUM COST=32767

MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=5
MINIMUM COST=3
MINIMUM COST=2
MINIMUM COST=32767
MINIMUM COST=5

MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=5
MINIMUM COST=3
MINIMUM COST=2
MINIMUM COST=2
MINIMUM COST=5

MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=5
MINIMUM COST=3
MINIMUM COST=2
MINIMUM COST=2
MINIMUM COST=5

******** GRAPH *********
MINIMUM COST=5

Process completed.*/

Fractional Knapsack Using Greedy Algorithm

import java.io.*;
class ksap
{
float p[];
float w[];
int n,m;

void getdata()throws IOException
{
BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));

System.out.println("how many objects");
n=Integer.parseInt(obj.readLine());
System.out.println("enter the capacity of bag");
m=Integer.parseInt(obj.readLine());

p=new float[n+1];
w=new float[m+1];

for(int i=1;i<=n;i++)
{
System.out.println("enter profit and weight");
p[i]=Float.parseFloat(obj.readLine());
w[i]=Float.parseFloat(obj.readLine());
}

}


void sort()
{
for(int i=1;i<=n-1;i++)
for(int j=1;j<=n-i;j++)
if ((p[j]/w[j])<(p[j+1]/w[j+1]))
{
float temp =p[j];
p[j]=p[j+1];
p[j+1]=temp;

float temp1=w[j];
w[j]=w[j+1];
w[j+1]=temp1;
}
}

float greedk()
{ int i;
float x[]=new float[n+1];

float u;
float pr=0;

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

{ x[i]=0;
u=m;
for( i=1;i<=n;i++)
{
if(w[i]<=u)
x[i]=1;
else
break;
u=u-(w[i]);
}



if( i<=n)
x[i]=u/w[i];
}
for(i=1;i<=n;i++)
pr=pr+(p[i])*(x[i]);
return pr;
}

}
class knapsackgreedy
{
public static void main(String args[])throws IOException

{
ksap ob=new ksap();
ob.getdata();
ob.sort();

float maxprofit;
maxprofit=ob.greedk();
System.out.println("Maximum profit="+maxprofit);
}
}

/* output
how many objects
3
enter the capacity of bag
26
enter profit and weight
12
15
enter profit and weight
20
9
enter profit and weight
30
11
Maximum profit=54.8
Process Exit...
*/

Kruskal Algorithm

import java.util.*;

class Edge
{
  int  v1,v2,w;
}
class Graph
{
  Edge edge[];
  int v,e;
  int p[];

  void creategraph()
  {
    int a,b,w;

    Scanner kbd = new Scanner(System.in);
    System.out.print("Enter number of vertices ");
    v = kbd.nextInt();
    System.out.print("Enter number of edges ");
    e = kbd.nextInt();
    edge = new Edge[e+1];
    for (int i = 1 ; i <= e ; i++)
      edge[i] = new Edge();
    for (int i = 1; i<= e ; i++)
    {
      System.out.print("Enter edge information ");
      a = kbd.nextInt();
      b = kbd.nextInt();
      System.out.print("Enter weight of this edge ");
      w = kbd.nextInt();
      edge[i].v1 =  a;
      edge[i].v2 =  b;
      edge[i].w =  w;
    }

  } // end creategraph

  void bubble()
  {
    for (int i = e-1 ; i >= 1 ; i--)
     for (int j = 1 ; j <= i ; j++)
      if (edge[j].w > edge[j+1].w)
      {
        Edge t = edge[j];
        edge[j] = edge[j+1];
        edge[j+1] = t;
      }
  }

  int find(int z) // find parent of z
  {
    while (p[z] != -1)
     z = p[z];

    return z;
  }
  void union(int u , int v)
  {
    p[v] = u;
  }
  void kruskal()
  {
   p = new int[v+1];
     for(int i = 1 ; i <= v  ; i++)
      p[i] = -1;
    int  mincost = 0 ;
    int  noofedgesadded = 0;
    for (int i = 1 ; i <= e && noofedgesadded != v-1 ; i++)
    {
      Edge t = edge[i];

      int start = t.v1;
      int end = t.v2;

      int p1 = find(start);
      int p2 = find(end);

      if (p1 != p2)
      {
        mincost += t.w;
        System.out.println("Vertex " + start + " to vertex " + end);
        union(p1,p2);
        noofedgesadded++;
       
      }
    } // for loop

    System.out.println("minimum cost = " + mincost);

  } // end of kruskal

} //end Graph class

public class Kruskal
{
  public static void main(String args[])
  {
    Graph g = new Graph();
    g.creategraph();
    g.bubble();
    g.kruskal();
  }
}
/*
 Output:
 Enter number of vertices 6
Enter number of edges 11
Enter edge information
1
2
Enter weight of this edge 2
Enter edge information 1
3
Enter weight of this edge 2
Enter edge information 1
6
Enter weight of this edge 6
Enter edge information 1
4
Enter weight of this edge 18
Enter edge information 2
4
Enter weight of this edge 7
Enter edge information 4
3
Enter weight of this edge 3
Enter edge information 6
5
Enter weight of this edge 5
Enter edge information 3
6
Enter weight of this edge 8
Enter edge information 3
5
Enter weight of this edge 4
Enter edge information 4
5
Enter weight of this edge 9
Enter edge information 2
3
Enter weight of this edge 1
Vertex 2 to vertex 3
Vertex 1 to vertex 2
Vertex 4 to vertex 3
Vertex 3 to vertex 5
Vertex 6 to vertex 5
minimum cost = 15
Process completed.*/

DIJKSTRA ALGORITHM

//IMPLEMENTATION OF DIJKSTRA ALGORITHM

import java.io.*;
class  Graph
{
 BufferedReader Bobj= new BufferedReader(new InputStreamReader(System.in));
 int g[][],v,e,d[],p[],visited[];
void Creategraph()throws IOException
       {
int a,b,w;   
     System.out.print("ENTER THE NO OF VETEX=");
          v=Integer.parseInt(Bobj.readLine());
          System.out.print("ENTER THE NO OF EDGES=");
          e=Integer.parseInt(Bobj.readLine());
          g=new int[v+1][v+1];
          for(int i=1;i<=v;i++)
             for(int j=1;j<=v;j++)
                  g[i][j]=0;
             for(int i=1;i<=e;i++)
          {System.out.println("ENTER THE EDGE INFORMATION\n");
            System.out.print("ENTER THE SORCE VERTEX=");
            a=Integer.parseInt(Bobj.readLine());
            System.out.print("ENTER THE DESTINATION VERTEX=");
            b=Integer.parseInt(Bobj.readLine());
            System.out.print("ENTER THE WEIGTH OF EDGE =");
            w=Integer.parseInt(Bobj.readLine());
            g[a][b]=g[b][a]=w;
      }
     }
void CallDijktra()throws IOException
{
 d=new int[v+1];
 p=new int[v+1];
 visited=new int[v+1];
 for(int i=1;i<=v;i++)
   {
        p[i]=0;
         visited[i]=0;
         d[i]=32767;
   }
   Dijktra();
   }
void Dijktra()throws IOException
{
  BufferedReader Bobj= new BufferedReader(new InputStreamReader(System.in));
     int dc,current,mincost=0,source,dest,c;
  System.out.print("\n\n\n\n\n\n\nENTER THE SOURCE VERTEX=");
    source=Integer.parseInt(Bobj.readLine());
    System.out.print("ENTER THE DESTINATION VERTEX=");
    dest=Integer.parseInt(Bobj.readLine());
  current=source;
  visited[current]=1;
  d[current]=0;
   dc=dest;
   while (current!=dest)
 {
    for(int i=1;i<=v;i++)
      {
     if(g[current][i]!=0 && visited[i]!=1)
          if (d[i]>g[current][i]+d[current])
                { 
d[i]=g[current][i]+d[current];
                    p[i]=current;
         }
     }
     for(int i=1;i<=v;i++)
 System.out.println("MINIMUM COST="+d[i]);System.out.println();
   int min=32767;
      for(int i=1;i<=v;i++)
      {
if (visited[i]!=1 && d[i]
         {
      min=d[i];
         current=i;
        }
   }
     visited[current]=1;
    }
  System.out.println("******** GRAPH *********");
  System.out.println("MINIMUM COST="+d[dest]);
  }
}
class DijktraDemo
{
 public static void main(String args[])throws IOException
  {
  Graph g=new Graph();
    g.Creategraph();
    g.CallDijktra();
   }
 }
/*Output:

ENTER THE NO OF VETEX=6
ENTER THE NO OF EDGES=10
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=1
ENTER THE DESTINATION VERTEX=2
ENTER THE WEIGTH OF EDGE =3
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=1
ENTER THE DESTINATION VERTEX=4
ENTER THE WEIGTH OF EDGE =2
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=1
ENTER THE DESTINATION VERTEX=6
ENTER THE WEIGTH OF EDGE =20
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=2
ENTER THE DESTINATION VERTEX=4
ENTER THE WEIGTH OF EDGE =8
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=2
ENTER THE DESTINATION VERTEX=3
ENTER THE WEIGTH OF EDGE =7
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=4
ENTER THE DESTINATION VERTEX=5
ENTER THE WEIGTH OF EDGE =3
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=4
ENTER THE DESTINATION VERTEX=6
ENTER THE WEIGTH OF EDGE =22
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=3
ENTER THE DESTINATION VERTEX=5
ENTER THE WEIGTH OF EDGE =6
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=5
ENTER THE DESTINATION VERTEX=6
ENTER THE WEIGTH OF EDGE =4
ENTER THE EDGE INFORMATION

ENTER THE SORCE VERTEX=4
ENTER THE DESTINATION VERTEX=6
ENTER THE WEIGTH OF EDGE =22
ENTER THE SOURCE VERTEX=1
ENTER THE DESTINATION VERTEX=6
MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=32767
MINIMUM COST=2
MINIMUM COST=32767
MINIMUM COST=20
MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=32767
MINIMUM COST=2
MINIMUM COST=5
MINIMUM COST=20

MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=10
MINIMUM COST=2
MINIMUM COST=5
MINIMUM COST=20
MINIMUM COST=0
MINIMUM COST=3
MINIMUM COST=10
MINIMUM COST=2
MINIMUM COST=5
MINIMUM COST=9
******** GRAPH *********
MINIMUM COST=9
Process completed.
*/

INTERNET ALGORITHM USING "KNUTHMORIES"

//IMPLEMENTATION OF INTERNET ALGORITHM USING KNUTHMORIES

import java.io.*;
import java.util.*;
class Knuthmories
{
    public int KMP(String T,String P)
    {
        int n=T.length();
        int m=P.length();
        int f[]=new int[10];
        int i=0;
        int j=0;
        f=failure(P,f);
        while (i
        {
            if (P.charAt(j)==T.charAt(i))
            {
                if(j==m-1)
                    return i-m+1;
                i++;
                j++;
            }
            else
            if(j>0)  
                j=f[j-1];
            else
            i++;
        }
        return -1;
    }
  
    public int[] failure(String P,int f[])
    {
        int i=1;
        int m=P.length();
        int j=0;
        f[0]=0;
        while (i
        {
            if (P.charAt(j)==P.charAt(i))
            {
                f[i]=j+1;
                i++;
                j++;
            }
            else if(j>0)
                j=f[j-1];
            else
            {
            f[i]=0;
            i++;
            }
        }
        return f;
    }
}
  
class Knuthmoriesdemo
{
    public static void main(String args[])throws IOException
    {
        String t,p;
        BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the string of your choice");
        t=obj.readLine();
        System.out.println("Enter the string to be compared");
        p=obj.readLine();
        Knuthmories b=new Knuthmories();
        int pos=b.KMP(t,p);
        System.out.println("The position of the string is :"+pos);
    }
}
              

/*OUTPUT
Enter the string of your choice
university
Enter the string to be compared
sity
The position of the string is :6
Process Exit...
*/

Job sequencing with dead lines by Greedy programming technique.

//This program performs job sequencing with dead lines by Greedy programming technique.

import java.io.*;
import java.util.*;
public class JobSeq
{
    public static InputStreamReader input=new InputStreamReader(System.in);
    public static BufferedReader br =new BufferedReader(input);
    static int job[][], n, maxd = 0;
    public static void main(String[] args)  throws IOException{
        System.out.print("Enter total number of jobs: ");
        n = Integer.parseInt( br.readLine() );
        job = new int[n][3];
        System.out.println("Enter job details: ");
        for(int i =0; i
            System.out.print("job #"+(i+1)+" :-\n\tProfit: ");
            job[i][0]=Integer.parseInt( br.readLine() );
            do
           {
                System.out.print("\tDead Line: ");
                job[i][1]=Integer.parseInt( br.readLine() );
                if(job[i][1] <= 0)
                {
                    System.out.print("\tInvalid Deadline!\nEnter Again\n");
                    continue;
                }
                else if(maxd < job[i][1])
                {
                    maxd = job[i][1];
                }
                break;
            }while(true);
            job[i][2]=i+1;
        }
        bubble_srt();
        JobSeq();
        int profit = 0;
        System.out.print("\nThe optimal solution is J = {" );
        for(int i=1; i<=k; i++)
        {
            System.out.print((job[J[i]-1][2])+", ");
            profit += job[J[i]-1][0];
        }
        System.out.println("\b\b } with a profit of "+ profit + ".");
    }
    public static void bubble_srt(){
        int i, j, t[][];
        t = new int[1][3];
        for(i = 0; i < n; i++)
            for(j = 1; j < (n-i); j++)
                if(job[j-1][0] < job[j][0])
                {
                    t[0] = job[j-1];
                    job[j-1]=job[j];
                    job[j]=t[0];
                }
    }
    static int J[], k;
    static void JobSeq()
{
        J = new int[maxd+1];
        int temjob[] = new int[n+1];
        int r;
        for(int i=1; i<=n; i++)
            temjob[i] = job[i-1][1];
        for(int i=0; i<=maxd; i++)
            J[i]=0;
        temjob[0] = J[0] = 0;
        J[1] = 1;
        k=1;
        for(int i=2; i<=n; i++)
        {
            r=k;
            while((temjob[J[r]] > temjob[i]) && (temjob[J[r]] != r))
                r--;
            if((temjob[J[r]] <= temjob[i]) && (temjob[i] > r) )
            {
                for(int q = k; q>= r+1; q--)
                    J[q+1] = J[q];
                J[r+1] = i; k++;
            }
        }
        return;
    }
}
/*Output:
Enter total number of jobs: 4
Enter job details:
 job #1 :-
    Profit: 100
    Dead Line: 2
job #2 :-
    Profit: 10
    Dead Line: 1
job #3 :-
    Profit: 15
    Dead Line: 2
job #4 :-
    Profit: 27
    Dead Line: 1

The optimal solution is J = {4, 1} with a profit of 127.
Process Exit...*/

Brute Force Algorithm(Internet algorithm)

import java.io.*;
class bf_fun
{
    int bf(String t,String p)
    {
        int n=t.length();
        int m=p.length();
        for(int i=0;i<=n-m;i++)
        {
            int j=0;
            while(j                j++;
            if(j==m)
            return i+1;
        }
        return -1;
    }
}

class bf
{
    public static void main(String args[])
    throws IOException
    {
        InputStreamReader input=new InputStreamReader(System.in);
        BufferedReader obj=new BufferedReader(input);
        System.out.println("Enter the string:");
        String s=obj.readLine();
        System.out.print("Enter the substring:");
        String ts=obj.readLine();
        bf_fun f=new bf_fun();
        int n=f.bf(s,ts);
        if (n!=-1)
            System.out.println("Pattern matched at position "+n);
           
        else
            System.out.println("No pattern matching");   
    }
}
/*

OUTPUT
Enter the string:
WHAT IS UR NAME
Enter the substring:IS
Pattern matched at position 6

*/

Selection Sort

import java.io.*;
public class SelectionSort
{
   
   public static void main(String args[])throws IOException
    {
           
            int ch;
            InputStreamReader cin=new InputStreamReader(System.in);
            BufferedReader obj=new BufferedReader (cin);
            System.out.println("Enter the no. element");
            int n=Integer.parseInt(obj.readLine());
            int a[]=new int[n];
            for(int i=0;i<=n-1;i++)
            {
                 System.out.println("Enter the element");
                 a[i]=Integer.parseInt(obj.readLine());
            }
            do
            {
                System.out.println("\nMenu\n1.Selection Sort\n2.exit");
                System.out.println("Enter the choice");
                ch=Integer.parseInt(obj.readLine());
                switch (ch)
                {
                case 1:Selectionsort(a,n);
                       System.out.println("Sorted Array is ");
                       for(int w=0;w<=n-1;w++)
                           System.out.println(a[w]);
                   break;
                case 2:
                  break;
                default:System.out.println("Wrong choice");
                  break;
                }
            }
            while(ch!=2);
    }
    public static void Selectionsort(int a[],int n)
    {
        int min,p,t;
        for(int i=0;i<=n-2;i++)
        {
            min=a[i];
            p=i;
            for(int j=i+1;j<=n-1;j++)
            {
                if (a[j]
                {
                    min=a[j];
                    p=j;
                }
            }
            t=a[p];
            a[p]=a[i];
            a[i]=t;
        }
    }
}
/***************************Output****************************************
Enter the no. element
5
Enter the element
6
Enter the element
10
Enter the element
50
Enter the element
-2
Enter the element
0

Menu
1.Selection Sort
2.exit
Enter the choice
1
Sorted Array is
-2
0
6
10
50

Menu
1.Selection Sort
2.exit
Enter the choice
2
Process Exit...
*/

Prim’s Algorithm

//Program  to  implement  Prim’s  Algorithm

import java.util.*;

import java.io.*;

class Graph

{

                int g[][],v,e;

                void create_graph() throws IOException

                {

                                int a,b,i,j,w;

                                BufferedReader in=new BufferedReader(new InputStreamReader(System.in));

                               

                                System.out.println("Enter no of vertices");

                                v=Integer.parseInt(in.readLine());

                                System.out.println("Enter no of edges");

                                e=Integer.parseInt(in.readLine());

                                g=new int [v+1][v+1];

                                for(i=1;i<=v;i++)

                                                for(j=1;j<=v;j++)

                                                                g[i][j]=0;

                                                for(i=1;i<=e;i++)

                                                {

                                                System.out.println("Enter no of information");

                                    a=Integer.parseInt(in.readLine()); 

            b=Integer.parseInt(in.readLine());

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

                                                w=Integer.parseInt(in.readLine());

                                                g[a][b]=g[b][a]=w;

                                                }

                }

               

                void prim()

                {

                                int current,d[],p[],visited[];

                                d=new int[v+1];

                                p=new int[v+1];

                                visited=new int[v+1];

                                for(int i=1;i<=v;i++)

                                {

                                                d[i]=32767;

                                                p[i]=0;

                                                visited[i]=0;

                                }

                                current=1;

                                d[current]=0;

                                visited[current]=1;

                                int c=1;

                                while (c!=v)

                                {

                                                for(int i=1;i<=v;i++)

                                                {

                                                                if(g[current][i]!=0 && visited[i]!=1)

                                                                                if (g[current][i]

                                                                                {

                                                                                                d[i]=g[current][i];

                                                                                                p[i]=current;

                                                                                }

                                                }

                                                int min=32767;

                                                for(int i=1;i<=v;i++)

                                                {

                                                                if (visited[i]!=1 && d[i]

                                                                {

                                                                                min=d[i];

                                                                                current=i;

                                                                }

                                                }

                                                visited[current]=1;

                                                c=c+1;

                                }

                                int mincost=0;

                                for(int i=1;i<=v;i++)

                                                mincost=mincost+d[i];

                                System.out.println("Minimum cost ="+mincost);

                }

}

class Graphtest

{

                public static void main(String args[]) throws IOException

                {

                                Graph G1=new Graph();

                                G1.create_graph();

                                G1.prim();

                }

               

}

/*OUTPUT:

Enter no of vertices 5

Enter no of edges 10

Enter no of information 1

2

Enter weight 5

Enter no of information 1

3

Enter weight 50

Enter no of information 2

3

Enter weight 15

Enter no of information 5

1

Enter weight 20

Enter no of information 5

3

Enter weight 25

Enter no of information 4

1

Enter weight 25

Enter no of information 1

3

Enter weight 55

Enter no of information 4

2

Enter weight 56

Enter no of information 2

5

Enter weight 58

Enter no of information 3

5

Enter weight 58

Minimum cost =65 Process Exit...*/

0/1 Knapsack problem using Dynamic Algo

import java.io.*;
class KSdyn
{
   public static void main(String args[])throws IOException
 {
   BufferedReader o=new BufferedReader(new InputStreamReader(System.in));
   int n,i,j;
  
   System.out.println("Enter the no of item");
   n=Integer.parseInt(o.readLine());
  
   int p[]=new int[n+1];
  
   int w[]=new int[n+1];
  
   System.out.println("Enter the profit");
   for(i=1;i<=n;i++)
   {
       p[i]=Integer.parseInt(o.readLine());
   }
   System.out.println("Enter the weight");
   for(j=1;j<=n;j++)
   {
       w[j]=Integer.parseInt(o.readLine());
   }
   System.out.println("enter the capacity of knapsack");
   int m=Integer.parseInt(o.readLine());
   knapsack(n,m,w,p);
 }
 static void knapsack(int n,int m,int w[],int p[])
 {
     int s[][]=new int[n+1][m+1];
    for(int W=0;W<=m;W++)
        s[0][W]=0;
    for(int i=0;i<=n;i++)
        s[i][0]=0;
    for(int i=1;i<=n;i++)
      for(int j=0;j<=m;j++)
        if (w[i]<=j)
         {
           if(p[i]+s[i-1][j-w[i]]>s[i-1][j])
              s[i][j]=p[i]+s[i-1][j-w[i]];
              else
              s[i][j]=s[i-1][j];
         }
         else
           s[i][j]=s[i-1][j];
     for(int i=0;i<=n;i++)
     
      {
      for(int j=0;j<=m;j++)
      {
      System.out.print(s[i][j]+" ");
      }
      System.out.println();
      }
        knapsack_item(s,w,n,m);  
 }
 static void knapsack_item(int s[][],int w[],int n,int m)
 {   int ans[]=new int[n];
     int i=n;
    int k=m;
    while (i>0&&k>0)
    {
        if (s[i][k]!=s[i-1][k])
        {
          ans[i]=1;
          k=k-w[i];
          //System.out.println("Item"+i+"is selected");
        }
        i--;
    }
   
    for(i=0;i
       if (ans[i]==1)
       {
           System.out.println("Item"+i+"is selected");
       }
   
 }
}/*Output:
Enter the no of item
4
Enter the profit
3
4
5
6
Enter the weight
2
3
4
5
enter the capacity of knapsack
5
0 0 0 0 0 0
0 0 3 3 3 3
0 0 3 4 4 7
0 0 3 4 5 7
0 0 3 4 5 7
Item1is selected
Item2is selected
*/             

MinMax using Greddy strategy

import java.io.*;
class Minmax
{
static int a[];
     static int[] findmax(int[] b,int low,int high)
     {
    int mid,min,max,x,y;
    int []temp1=new int[2];
    int []temp2=new int[2];
   
    if (low==high)
    {
        temp1[0]=b[low];
        temp1[1]=b[high];
    }
    else if (high-low==1)
    {
        if (b[low]
        {
            temp1[0]=b[low];
            temp1[1]=b[high];
        }
            else
            {
                temp1[0]=b[high];
            temp1[1]=b[low];
            }
    }
        else
        {
        mid=(low+high)/2;
        temp1=findmax(b,low,mid);
        temp2=findmax(b,mid+1,high);
        x=min(temp1[0],temp2[0]);
        y=max(temp1[1],temp2[1]);
        temp1[0]=x;
        temp1[1]=y;
       
        }
       
    return temp1;   
    }
static int min(int x,int y)
{
    if(x
        return x;
    else
        return y;   
}
static int max(int x,int y)
{
    if(x
        return y;
    else
        return x;   
}
public static void main(String args[]) throws IOException
{
    Minmax m=new Minmax();
    int[] sol=new int[2];
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    System.out.println("Enter no of elements:");
    int n=Integer.parseInt(br.readLine());
    a=new int[n];
    System.out.println("Enter the elements of array:");
    for(int i=0;i
    {
        a[i]=Integer.parseInt(br.readLine());
    }
    sol=findmax(a,0,a.length-1);
     System.out.println("min element:"+sol[0]);
     System.out.println("max element:"+sol[1]);
}
}
/*Output:
Enter no of elements:
7
Enter the elements of array:
25 100 63 7 96 78 49
min element:7
max element:100
Process completed. */

nQueen

//Program to implement n Queen
import java.io.*;
class Nqueen
{
    int n;
    int x[];
    void read()throws IOException
    {
        InputStreamReader in=new InputStreamReader(System.in);
        BufferedReader cin=new BufferedReader(in);
        System.out.println("enter number of queens");
        n=Integer.parseInt(cin.readLine());
        x=new int [n+1];
    }
    boolean place(int k,int i)
    {
        for(int j=1;j<=k-1;j++)
        {
            if(x[j]= =i || Math.abs(x[j]-i)= =Math.abs(k-j))
           
                return false;
        }
        return true;
    }
    void nqueen(int k)
    {
        for(int i=1;i<=n;i++)
        {
            if (place(k,i))
            {
                x[k]=i;
                if (k==n)
                {
                    for(int j=1;j<=n;j++)
                        System.out.print(x[j]+"  ");
                        System.out.println();
                }
               
                else
               
                nqueen(k+1);
            }
        }
    }
}
class Nqueentest
{
    public static void main (String args[])throws IOException
    {
        Nqueen nq=new Nqueen();
        nq.read();
        nq.nqueen(1);
    }
}

/*OUTPUT:
Enter number of queens
4 
2  4  1  3 
3  1  4  2 
Process Exit...*/

Strassen Multiplication

import java.util.*;
import java.io.*;
class strassen
{
    public static void read(int x[][],int n)throws IOException
    {
        BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter matrix");
        for(int i=0;i
        {
            for(int j=0;j
            {
                x[i][j]=Integer.parseInt(b.readLine());
            }
           
        }
    }
    public static void display(int x[][],int n)
    {
        for(int i=0;i
        {
            for(int j=0;j
            {
                System.out.print(x[i][j]+" ");
                    System.out.println(" ");
               
           
            }
        }
    }
    public static int[][] add(int x[][],int y[][],int n)
    {
        int z[][]=new int[n][n];
        for(int i=0;i
        {
            for(int j=0;j
            {
                z[i][j]=x[i][j]+y[i][j];
            }
        }
        return z;
    }
    public static int[][] prod(int x[][],int y[][])
    {
        int z[][]=new int[2][2];
        int p,q,r,s,t,u,v;
        p=(x[0][0]+x[1][1])*(y[0][0]+y[1][1]);
        q=(x[1][0]+x[1][1])*y[0][0];
        r=x[0][0]*(y[0][1]-y[1][1]);
        s=x[1][1]*(y[1][0]-y[0][0]);
        t=(x[0][0]+x[0][1])*y[1][1];
        u=(x[1][0]-x[0][0])*(y[0][0]+y[0][1]);
        v=(x[0][1]-x[1][1])*(y[1][0]+y[1][1]);
        z[0][0]=p+s-t+v;
        z[0][1]=r+t;
        z[1][0]=q+s;
        z[1][1]=p+r-q+u;
        return z;
    }
    public static void store(int p[][],int res[][],int is,int ie,int js,int je)
    {
        for(int i=is,i1=0;i
        {
            for(int j=is,j1=0;j
            {
                res[i][j]=p[i1][j1];
            }
        }
    }
    public static int[][] mult(int x[][],int y[][],int n)
    {
        if(n==2)
            return(prod(x,y));
        int x1[][]=new int[n/2][n/2];
        int x2[][]=new int[n/2][n/2];
        int x3[][]=new int[n/2][n/2];
        int x4[][]=new int[n/2][n/2];
        int y1[][]=new int[n/2][n/2];
        int y2[][]=new int[n/2][n/2];
        int y3[][]=new int[n/2][n/2];
        int y4[][]=new int[n/2][n/2];
        for(int i=0;i
        {
            for(int j=0;j
            {
               
                x1[i][j]=x[i][j];
                y1[i][j]=y[i][j];
               
            }
        }
        for(int i=0,i1=0;i
        {
            for(int j=n/2,j1=0;j
            {
                x2[i1][j1]=x[i][j];
                y2[i1][j1]=y[i][j];
       
            }
        }
        for(int i=n/2,i1=0;i
        {
            for(int j=0,j1=0;j
            {
                x3[i1][j1]=x[i][j];
                y3[i1][j1]=y[i][j];
            }
        }
        for(int i=n/2,i1=0;i
        {
            for(int j=n/2,j1=0;j
            {
                x4[i1][j1]=x[i][j];
                y4[i1][j1]=y[i][j];
            }
        }
        int k[][][]=new int[8][][];
        k[0]=mult(x1,y1,n/2);
        k[1]=mult(x2,y3,n/2);
        k[2]=mult(x1,y2,n/2);
        k[3]=mult(x2,y4,n/2);
        k[4]=mult(x3,y1,n/2);
        k[5]=mult(x4,y2,n/2);
        k[6]=mult(x3,y2,n/2);
        k[7]=mult(x4,y4,n/2);
        int partial[][][]=new int[4][][],j=0;
        for(int i=0;i
        {
            partial[j]=add(k[i],k[i+1],n/2);
            j++;
        }
        int result[][]=new int[n][n];
        store(partial[0],result,0,n/2,0,n/2);
        store(partial[1],result,0,n/2,n/2,0);
        store(partial[0],result,n/2,n,0,n/2);
        store(partial[0],result,n/2,n,n/2,n);
        return result;
        }
}
class StrassenDemo
{
    public static void main(String args[])throws IOException
    {
            BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
            System.out.println("Enter the order of the matrix");
            int n=Integer.parseInt(b.readLine());
            int a[][]=new int[n][n];
            int d[][]=new int[n][n];
            strassen s=new strassen();
            s.read(a,n);
            s.read(d,n);
            int c[][]=s.mult(a,d,n);
            System.out.println("Strassen Matrix Multiplication\nResult Matrix");
            s.display(c,n);
        }
}
/*Output
Enter the order of the matrix
2
Enter matrix
5
6
7
4
Enter matrix
4
2
1
5
Strassen Matrix Multiplication
Result Matrix
26 
40 
32 
34 
*/

Merge Sort

//Aim:To implement Merge Sort/*--------------------------------------------------*/

import java.io.*;
class Merge
{
    void simplemerge(int a[],int f,int s, int t)
    {
        int i,j,temp[],k;
        temp=new int[t-f+1];
        i=f;
        j=s;
        k=-1;
        while (i<=s-1 && j<=t)
        {
            if (a[i]
                temp[++k]=a[i++];
            else
                temp[++k]=a[j++];
        }
        for(int w=i;w<=s-1;w++)
        {
            k++;
            temp[k]=a[w];
        }
        for(int w=0;w<=k;w++)
        {
            a[f+w]=temp[w];
        }
    }
    void mergesort(int a[],int l,int r)
    {
        int mid;
        if (l
        {
            mid=(l+r)/2;
            mergesort(a,l,mid);
            mergesort(a,mid+1,r);
            simplemerge(a,l,mid+1,r);
        }
    }
}
class Test
{
     public static void main(String args[])throws Exception
     {
         DataInputStream d=new DataInputStream(System.in);
        System.out.println("How many elements:");
        int n=Integer.parseInt(d.readLine());
        int a[]=new int[n];
        System.out.println("enter the elements:");
        for(int i=0;i<=a.length-1;i++)
        {
            a[i]=Integer.parseInt(d.readLine());
        }
        Merge m=new Merge();
        int l=0;
        int r=a.length-1;
        m.mergesort(a,l,r);
        System.out.println("Sorted Array:");
        for(int i=0;i
        {
        System.out.println(a[i]);
       
        }
     }
}           
/*Output:
How many elements:
5
enter the elements:
41 38 6 98 57
Sorted Array:
6 38 41 57 98
Process completed.*/