34. GRAPH COLORING PROBLEM

//GRAPH COLORING PROBLEM
import java.io.*;
import java.util.*;
class Gr_Color
{
 public int G[][],n,m,edges;
 int color_tab[];
 public Gr_Color(int MAX)
 {
System.out.println("\n\n\t Graph Coloring ");
G=new int[MAX][MAX];
  color_tab=new int[MAX];
for(int i=0;i<MAX;i++)
{
for(int j=0;j<MAX;j++)
{
 G[i][j]=0;
 color_tab[i]=0;
}
                }
}

33. STRASSEN'S MATRIX MULTIPLICATION

//STRASSEN'S MATRIX MULTIPLICATION
import java.io.*;
public class Strassen
{
public static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
public Strassen() throws IOException
{
int n;
int[][] a, b, c;
System.out.print("Enter the number or rows or colums: ");
n = Integer.parseInt(br.readLine());
a = new int[n][n];
b = new int[n][n];
c = new int[n][n];

32. PRIM'S ALGORITHM FOR MST

//PRIM’S ALGORITHM
import java.util.*;
class Prim
{
public static Scanner br =new Scanner(System.in);
static int [][] G;
static int [][] t;
static int [] near;
static int n;
static int mincost = 0;
static int k, l;

31. KRUSKAL ALGORITHM FOR MST

//KRUSKAL ALGORITHM
import java.util.*;
class Kruskal
{
public static Scanner sc =new Scanner(System.in);
static int [][] G;
static int [][] t;
static boolean [][] in;
static boolean [][] temp;
static int n;
static int mincost = 0;
static int k, l, num_ed=0;

30. JOB SEQUENCING WITH DEADLINE

//JOB SEQUENCING WITH DEADLINE

import java.io.*;

import java.util.*;

class jobsequence

{

public static void main(String args[])

{

int m,n,i,j,temp,p,max=0,total_profit=0;

int profit[]=new int[20];

int deadline[]=new int[20];

int sort[]=new int[20];

//int total_profit[]=new int[20];

int lp[]=new int[20];

int up[]=new int[20];

int pos[]=new int[20];

Scanner s=new Scanner(System.in);

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

n=s.nextInt();

29. N QUEEN PROBLEM

//N QUEEN PROBLEM

import java.io.*;

public class Queens {

public static boolean isConsistent(int[] q, int n) {

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

if (q[i] == q[n]) return false; // same column

if ((q[i] - q[n]) == (n - i)) return false; // same major diagonal

if ((q[n] - q[i]) == (n - i)) return false; // same minor diagonal

}

return true;

}

28. MULTISTAGE GRAPHS

//MULTISTAGE

import java.io.*;

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;//equal to infinity

int min_vertex=0;

27. KMP PATTERN MATCHING ALGORITHM

//KNUTH-MORRIS PRATT PATTERN MATCHING ALGORITHM
public class KMP {
private final int R;
private int[][] dfa;
private char[] pattern;
private String pat;
public KMP(String pat) {
this.R = 256;
this.pat = pat;
int M = pat.length();
dfa = new int[R][M];
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][X];
dfa[pat.charAt(j)][j] = j+1;
X = dfa[pat.charAt(j)][X];
}
}

26. TRAVELLING SALESPERSON PROBLEM

//TRAVELLING SALESMAN PROBLEM
import java.util.*;
import java.text.*;
class TSP
{
int weight[][],n,tour[],finalCost;
final int INF=1000;
public TSP()
{
Scanner s=new Scanner(System.in);
System.out.println("Enter no. of nodes:=>");
n=s.nextInt();
weight=new int[n][n];
tour=new int[n-1];
for(int i=0;i<n;i++)

25. BANKER'S ALGORITHM

//BANKER’S ALGORITHM
import java.util.*;
class Bankersalgorithm
{
void disp(int m,int n,int alloc[][],int max[][],int avble[],int need[][])
{
char res[]={'A','B','C','D','E','F','G','H','I','J'};
int i,j;
System.out.println("\n\tALLOCATION\tMAX\tNEED\tAVAILABLE");
System.out.println("\n\t\t");
for(i=0;i<4;i++)
{
for(j=0;j<m;j++)
System.out.print(" "+res[j]);
System.out.print("\t\t");
}