Graph Coloring Problem -- GCP

import java.util.*;

import java.io.*;

class demo

{

int m,n;

int x[],graph[][];

void mcolor(int k)

{

int i;

while(1)

{

callnextvalue(k);

if(x[k]==o)break;

if(k==n)

{

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

System.out.println(" "+x[i]);

System.out.println();

}

else

mcolor(k+1);

}

}

All Pair Shortest Path

import java.io.*;

import java.util.*;

class graph

{

        int g[][],v,e,i,j,k;

        void creatgraph()

        {

                        Scanner s=new Scanner(System.in);

                        int a,b,w;

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

                        v=s.nextInt();

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

                        e=s.nextInt();

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

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

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

        g[i][j]=32767;

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

        g[i][i]=0;

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

                        {

                                        System.out.println("Enter edge information:");

                                        a=s.nextInt();

                                        b=s.nextInt();

Boyer Moore Algorithm

import java.util.*;

class Pattern3

{

                int bmMatch(String text,String pattern)

                {  

                                int last[] = buildLast(pattern);

                                int n = text.length(); 

                                int m = pattern.length();

                                int i = m-1; 

                                if (i > n-1)  

                                                return -1; // no match  

                                int j = m-1;

                                do

                                {   

                                if (pattern.charAt(j) == text.charAt(i)) 

                                                if (j == 0)   

                                                                return i; // match     

                                                else

                                                {

                                                                // looking-glass technique 

                                                                i--;   

                                                                j--;     

                                                } 

                                else

                                {

Brute Force Pattern Matching

import java.util.*;

class Pattern

{

                 int brute(String text,String pattern)

                {

                                int n = text.length();    //n is the length of text

                                int m = pattern.length(); // m is length of pattern

                                int j;

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

                                {  

                                                j = 0;

                                                while ((j < m) && (text.charAt(i+j) == pattern.charAt(j)) )  

                                                j++;  

                                                if (j == m)  

                                                                return i;   // match at i

                                }

                                return -1;   // no match

                }// end of brute()

}

public class BruteForce

{

                public static void main(String args[])

                {

Hamiltonians Cycle

import java.io.*;

class Hamilton

{

                void Nextvalue(int k,int n,int g[][],int x[])

                {

                                int j;

                                do

                                {

                                                x[k]=(x[k]+1)%(n+1);

                                                if(x[k]==0)

                                                return;

                                                if(g[x[k-1]][x[k]]!=0)

                                                {

                                                                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]]!=0)))

                                                                                return;

                                                                }

                                                }

                                }

                                while(true);

Job Sequencing With Deadline

import java.io.*;

class job

{

        static void JS(int d[],int j[],int n,int p[])throws IOException

        {

                        int profit=0;

                        j[1]=1;

                     int              k=1,r;

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

                        {

                                         r=k;

                                        while((d[j[r]]>d[i]) && (d[j[r]]!=r))

                                        r=r-1;

                                        if(d[j[r]]<=d[i] && d[i]>r)

                                        {

                                                        for(int q=(k);q>=(r+1);q--)

                                                        {

                                                                        if(q==-1)

                                                                        break;

                                                        j[q+1]=j[q];

                                            }

                                                        j[r+1]=i;

                                                        k=k+1;

                                        }

                        }

Knapsack – Greedy algorithm

import java.io.*;

class greedy

{

        int n;

        double m,p[],w[];

        void read()throws IOException

        {

                        DataInputStream d=new DataInputStream(System.in);

                        System.out.println("enter no of objects");

                        n=Integer.parseInt(d.readLine());

                        System.out.println("enter total capacity");

                        m=Double.parseDouble(d.readLine());

                        p=new double[n+1];

                        w=new double[n+1];

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

                        {

                                        System.out.println("enter weight of obj "+i);

                                        w[i]=Double.parseDouble(d.readLine());

                                        System.out.println("enter profit of obj "+i);

                                        p[i]=Double.parseDouble(d.readLine());

                        }

        }

        void sort()

        {

                        for(int i=n-1;i>=1;i--)

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

                       

0/1 Knapsack – Dynamic Programming

import  java.util.*;

class knapsack_dynamic

{

                int n,p[],w[],capacity;

                void read()

                {

                                Scanner k=new Scanner(System.in);

                                System.out.println("Enter no. of objects:");

                                n=k.nextInt();

                                System.out.println("Enter capacity of knapsack:");

                                capacity=k.nextInt();

                                //create p and w array of size n+1

                               

                                p=new int[n+1];

                                w=new int[n+1];

                               

                                //read array w and p from 1 to n

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

                                {

                                                System.out.println("Enter weight of object " +i);

                                                w[i]=k.nextInt();

                                                System.out.println("Enter profit of object "+i);

                                                p[i]=k.nextInt();

                                                }

                                }//end read

                               

                                void fill()

Kruskal’s algorithm

import java.io.*;

  import java.util.*;

  class Graph

  {

  int i,n; //no of nodes

  int noe; //no edges in the graph

  int graph_edge[][]=new int[100][4];d

  int tree[][]=new int [10][10];

  int sets[][]=new int[100][10];

  int top[]=new int[100];

  int cost=0;

  void read_graph()

  {

                System.out.print("Enter the no. of nodes in the undirected weighted graph ::");

                n=getNumber();

                noe=0;

                System.out.println("Enter the weights for the following edges ::\n");

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

                {

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

                                {

                                                System.out.print(" < "+i+" , "+j+" > ::");

                                                int w;

                                                w=getNumber();

                                                if(w!=0)

                                                {

Sum Of Subsets

import java.util.*;

import java.io.*;

class Demo

{

int m;

int w[],n,x[];

public static void main(String arg[])

{

Scanner in=new Scanner(System.in);

int i,r=0;

System.out.println("Enter Enter the no. elements of set");

n=in.nextInt();

System.out.println("Enter the elements");

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

{

w[i]=in.nextInt();

r=r+w[i];

}

System.out.println("Enter the sum to be computed");

m=in.nextInt();

System.out.println("Subsets whose sum is "+m+"are as follows");

Sum0fSub(0,0,r);

Single Source Shortest Path

import java.io.*;

class Graph

{   DataInputStream d=new DataInputStream(System.in);

                int e,v,g[][];

                void creategraph()throws IOException

                {

                                int a,b,i,j;int source,dest;

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

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

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

                                e=Integer.parseInt(d.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++)

                                {

                                                int w;

                                                System.out.println("enter two vertices of edge "+i);

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

Prim's algorithm

import java.io.*;

 import java.util.*;

 class Graph

 {

                int weight[][]=new int[20][20];

                int visited[]=new int[20];

                int d[]=new int[20];

                int p[]=new int[20];

                int v,e;

                int getNumber()

                {

                                String str;

                                int ne=0;

                                InputStreamReader input=new InputStreamReader(System.in);

                                BufferedReader in=new BufferedReader(input);

                                try

                                {

                                str=in.readLine();

                                ne=Integer.parseInt(str);

                                }

                                catch(Exception e)

                                {

                                System.out.println("I/O Error");

                                }

N-Queen Problem

import java.io.DataInputStream;  

import java.math.*;  

class nQueens

{

                public static void main(String arg[])

                {

                                int n=0;

                                int x[ ]= new int[8];

                                int count=0;

                                DataInputStream in = new DataInputStream(System.in);

                                System.out.print("\n\t\t\t\tN-Queens Problem\n\n");

                               

                try

                                {

                                    System.out.print("Enter value of n  : ");

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

                                }

                               

                                catch(Exception e) {   System.out.print("I/O Error");   }

                                nqueens(1,n,x,count);

Multi-Stage Graph

import java.util.*;

class Multistage{

    public int stages,stage_vertices[],c[][];

    public int cost[],p[],n;

    public Multistage(int max){

    c=new int [max][max];

    stage_vertices=new int[max];

    cost=new int[max];

    p=new int[max];

    }

   

    public int Get_min(int s,int n){

    int min=9999;

    int min_vertex=0;

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

    if(min>c[s][i]+cost[i]){

    min=c[s][i]+cost[i];

Tower of Hanoi Solution

import java.util.Scanner;

public class HanoiTowerSoln

{

    static void MoveDisc(int whichdisc,char frompeg,char topeg)

    {

        System.out.println("Move ring " + whichdisc + " from " + frompeg + " to " + topeg);

    }

    static void MoveTower(int height,char frompeg,char topeg,char usingpeg)

    {

        if(height>0)

        {

            MoveTower(height-1,frompeg,usingpeg,topeg);

            MoveDisc(height,frompeg,topeg);

            MoveTower(height-1,usingpeg,topeg,frompeg);

        }

    }

    public static void main(String[] args)

    {

Tower of Hanoi iteration Count

import java.util.*;

public class HanoiTowerCount

{

                static double hanoi(int n)

        {

            if (n==0)

                return 1;

            else

                return(2*hanoi(n-1));

                }

                public static void main(String[] args)

    {

                                Scanner in=new Scanner(System.in);

                                System.out.println("Enter no. of rings please");

                                int n=in.nextInt();

                                double ans=hanoi(n);

                                System.out.println(--ans);

    }

}

Java implementation of Postfix Evaluation

import java.util.Scanner;

class PostFixEval

{

    boolean isDigit(char ch)

    {

        if(ch>='0'&& ch<='9')

            return true;

        else

            return false;

    }

    void Eval(String expr)

    {

        int position;

        char c;

        double num1,num2,value;

        Stack_Num s=new Stack_Num();

        s.top=-1;

        for(position=0;position<expr.length(); position++)

        {

Java implementation of Infix to Postfix

import java.util.Scanner;

public class InFixToPostFix

{

    int Priority(char TopSym,char Sym)

    {

        if(TopSym=='(')

            return 0;

        if(Sym=='(')

            return 0;

        if(Sym==')')

            return 1;

        if((TopSym=='*'||TopSym=='/'))

            return 1;

        if((TopSym== '+'||TopSym=='-')&&(Sym=='-'||Sym=='+'))

            return 1;

        if((TopSym== '+'||TopSym=='-')&&(Sym=='*'||Sym=='/'))

            return 0;

        else

            return 1;

    }

    boolean isOperand(char Sym)

    {