BitsToGather

Friday, April 15, 2011

Selection sort

import java.util.Scanner;

class SelectionSort

{

static void Selection(int x[],int n)

{

int i,indx,j,large;

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

{

large=x[0];

indx=0;

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

if(x[j]>large)

{

large=x[j];

indx=j;

}

x[indx]=x[i];

x[i]=large;

for(int v=0;v<n;v++)

System.out.print("\t"+x[v]);

System.out.println();

}

public static void main(String args[ ])

{

int i,n=10;

Scanner in = new Scanner(System.in);

System.out.print("Enter how many numbers to be sorted : ");

n = in.nextInt();

int x[]=new int[n];

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

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

x[i] = in.nextInt();

Selection(x,n);

System.out.println("\nSorted Elements are :");

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

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

}

Thursday, April 14, 2011

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;

{

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;

{

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)

{

C implementation of Bresenham's Line Drawing Algorithm

Hello friends,following is the another program from Computer Graphics subject for Bresenham's Line Drawing Algorithm .Screenshoots shown are taken by running the programs in virtual machine os.

PROGRAM CODE

#include<stdio.h>

#include<conio.h>

#include<math.h>

#include<graphics.h>

int round(float x);

void bresenham(int x1,int y1,int x2,int y2,int color);

void main ()

{

clrscr();

int gd=DETECT,gm;

int x1,x2,y1,y2;

printf("\nEnter Starting Point(X1,Y1) :");

scanf("%d%d",&x1,&y1);

printf("\nEnter End Point(X2,Y2) :");

scanf("%d%d",&x2,&y2);

clrscr();

initgraph(&gd,&gm,"C:\\TC\\BGI");