Implement Bellman ford algorithm in java.

Bellman ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative.

Bellman ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source.

If there is no such cycle,the algorithm produces the shortest paths and their weights.

lets implement Bellman ford algorithm in java,

 

import java.util.Scanner;
 
public class BellmanFord
{
    private int distances[];
    private int numberofvertices;
    public static final int MAX_VALUE = 999;
 
    public BellmanFord(int numberofvertices)
    {
        this.numberofvertices = numberofvertices;
        distances = new int[numberofvertices + 1];
    }
 
    public void BellmanFordEvaluation(int source, int adjacencymatrix[][])
    {
        for (int node = 1; node <= numberofvertices; node++)
        {
            distances[node] = MAX_VALUE;
        }
 
        distances[source] = 0;
        for (int node = 1; node <= numberofvertices - 1; node++)
        {
            for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
            {
                for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++) { if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE) { if (distances[destinationnode] > distances[sourcenode] 
                                + adjacencymatrix[sourcenode][destinationnode])
                            distances[destinationnode] = distances[sourcenode]
                                + adjacencymatrix[sourcenode][destinationnode];
                    }
                }
            }
        }
 
        for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
        {
            for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++) { if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE) { if (distances[destinationnode] > distances[sourcenode]
                           + adjacencymatrix[sourcenode][destinationnode])
                        System.out.println("The Graph contains negative egde cycle");
                }
            }
        }
 
        for (int vertex = 1; vertex <= numberofvertices; vertex++)
        {
            System.out.println("distance of source  " + source + " to "
                      + vertex + " is " + distances[vertex]);
        }
    }
 
    public static void main(String... arg)
    {
        int numberofvertices = 0;
        int source;
        Scanner scanner = new Scanner(System.in);
 
        System.out.println("Enter the number of vertices");
        numberofvertices = scanner.nextInt();
 
        int adjacencymatrix[][] = new int[numberofvertices + 1][numberofvertices + 1];
        System.out.println("Enter the adjacency matrix");
        for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
        {
            for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
            {
                adjacencymatrix[sourcenode][destinationnode] = scanner.nextInt();
 	        if (sourcenode == destinationnode)
                {
                    adjacencymatrix[sourcenode][destinationnode] = 0;
                    continue;
                }
                if (adjacencymatrix[sourcenode][destinationnode] == 0)
                {
                    adjacencymatrix[sourcenode][destinationnode] = MAX_VALUE;
                }
            }
        }
 
        System.out.println("Enter the source vertex");
        source = scanner.nextInt();
 
        BellmanFord bellmanford = new BellmanFord(numberofvertices);
        bellmanford.BellmanFordEvaluation(source, adjacencymatrix);
        scanner.close();	
    }
}

OUTPUT:
bellman

Implement the Boyer Moore string matching algorithm.

The Boyer-Moore algorithm was developed by R.S.Boyerand J.C.Moore in 1977.

The Boyer-Moore algorithm scans the characters of the pattern from right to left beginning with the rightmost one and performs the comparisons from right to left.

In case of a mismatch or a complete match of the whole pattern it uses two pre-computed functions to shift the window to the right.

lets see java program that implement the Boyer Moore string matching algorithm.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class BoyerMoore
{
    public void findPattern(String t, String p)
    {
        char[] text = t.toCharArray();
        char[] pattern = p.toCharArray();
        int pos = indexOf(text, pattern);
        if (pos == -1)
            System.out.println("\nNo Match\n");
        else
            System.out.println("Pattern found at position : "+ pos);
    }
    public int indexOf(char[] text, char[] pattern) 
    {
        if (pattern.length == 0) 
            return 0;
        int charTable[] = makeCharTable(pattern);
        int offsetTable[] = makeOffsetTable(pattern);
        for (int i = pattern.length - 1, j; i < text.length;) 
        {
            for (j = pattern.length - 1; pattern[j] == text[i]; --i, --j) 
                     if (j == 0) 
                    return i;
 
              i += Math.max(offsetTable[pattern.length - 1 - j], charTable[text[i]]);
        }
        return -1;
      }
      private int[] makeCharTable(char[] pattern) 
      {
        final int ALPHABET_SIZE = 256;
        int[] table = new int[ALPHABET_SIZE];
        for (int i = 0; i < table.length; ++i) 
               table[i] = pattern.length;
        for (int i = 0; i < pattern.length - 1; ++i) table[pattern[i]] = pattern.length - 1 - i; return table; } private static int[] makeOffsetTable(char[] pattern) { int[] table = new int[pattern.length]; int lastPrefixPosition = pattern.length; for (int i = pattern.length - 1; i >= 0; --i) 
        {
            if (isPrefix(pattern, i + 1)) 
                   lastPrefixPosition = i + 1;
              table[pattern.length - 1 - i] = lastPrefixPosition - i + pattern.length - 1;
        }
        for (int i = 0; i < pattern.length - 1; ++i) 
        {
              int slen = suffixLength(pattern, i);
              table[slen] = pattern.length - 1 - i + slen;
        }
        return table;
    }
    private static boolean isPrefix(char[] pattern, int p) 
    {
        for (int i = p, j = 0; i < pattern.length; ++i, ++j) if (pattern[i] != pattern[j]) return false; return true; } private static int suffixLength(char[] pattern, int p) { int len = 0; for (int i = p, j = pattern.length - 1; i >= 0 && pattern[i] == pattern[j]; --i, --j) 
               len += 1;
        return len;
    }
    public static void main(String[] args) throws IOException
    {    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Boyer Moore Algorithm Test\n");
        System.out.println("\nEnter Text\n");
        String text = br.readLine();
        System.out.println("\nEnter Pattern\n");
        String pattern = br.readLine();
        BoyerMoore bm = new BoyerMoore(); 
        bm.findPattern(text, pattern);     
    }
}

OUTPUT:
booyer

Implement the Rabin–Karp matcher string matching algorithm.

Here,first I explains that what is String matching? and then i will write a java program to implement the Rabin – Karp matcher string matching algorithm.

What is String matching?

String matching is the technique of finding the instance of a character pattern in a given string.

  • Rabin-Karp algorithm is used for finding the numeric pattern in a given text.

now,lets see java program to implement the Rabin – Karp matcher string matching algorithm.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Random;
import java.math.BigInteger;
 
public class RabinKarp 
{
    private String pat; 
    private long patHash;    
    private int M;  
    private long Q; 
    private int R;   
    private long RM;          
 
    public RabinKarp(String txt, String pat) 
    {
        this.pat = pat;      
        R = 256;
        M = pat.length();
        Q = longRandomPrime();
        RM = 1;
        for (int i = 1; i <= M-1; i++)
           RM = (R * RM) % Q;
        patHash = hash(pat, M);
        int pos = search(txt);
        if (pos == -1)
            System.out.println("\nNo Match\n");
        else
            System.out.println("Pattern found at position : "+ pos);
    } 
    private long hash(String key, int M)
    { 
        long h = 0; 
        for (int j = 0; j < M; j++) 
            h = (R * h + key.charAt(j)) % Q; 
        return h; 
    } 
    private boolean check(String txt, int i) 
    {
        for (int j = 0; j < M; j++) 
            if (pat.charAt(j) != txt.charAt(i + j)) 
                return false; 
        return true;
    }
    private int search(String txt) 
    {
        int N = txt.length(); 
        if (N < M) return N;
        long txtHash = hash(txt, M); 
        if ((patHash == txtHash) && check(txt, 0))
            return 0;
        for (int i = M; i < N; i++) 
        {
            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q; 
            txtHash = (txtHash * R + txt.charAt(i)) % Q; 
            int offset = i - M + 1;
            if ((patHash == txtHash) && check(txt, offset))
                return offset;
        }
     
        return -1;
    }
   
    private static long longRandomPrime() 
    {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }
   
    public static void main(String[] args) throws IOException
    {    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Rabin Karp Algorithm Test\n");
        System.out.println("\nEnter Text\n");
        String text = br.readLine();
        System.out.println("\nEnter Pattern\n");
        String pattern = br.readLine();
        System.out.println("\nResults : \n");
        RabinKarp rk = new RabinKarp(text, pattern);        
    }
}

OUTPUT:
rabin

Write a program that implement divide and conquer method to find the maximum and minimum of n elements.Use recursion to implement the divide and conquer scheme.

First we see what is divide and conquer method in computer science ? and implement divide and conquer method to find the maximum and minimum of n elements in java language.

What is divide and conquer method in computer science ?

Divide : divide the problem into a number of sub problems that are smaller instance of the same problem.

Conquer : conquer the sub problems by solving  them recursively.

Combine : combine the solution to the sub problems into the solution for the original problem.

now,lets implement divide and conquer method to find the maximum and minimum of n elements in java language.

 

public class MaxMin {
    static MaxMin m=new MaxMin();
    static int max,min;

    public static void main(String ar[])
    {
        int a[]={17,155,99,7,15,11,10,1};
        MaxMin.max=MaxMin.min=a[0];
        int[] getMaxMin=m.MaxMin(a, 0, a.length-1, a[0], a[0]);
        System.out.println("Max : "+getMaxMin[0]+"\nMin : "+getMaxMin[1]);
    }

    public int[] MaxMin(int[] a,int i,int j,int max,int min)
    {
        int mid,max1,min1;
        int result[]=new int[2];
        //Small(P)
        if (i==j) { max = min = a[i]; }
     else if (i==j-1) // Another case of Small(P)
          {
                if (a[i] < a[j]) { this.max = getMax(this.max,a[j]); this.min = getMin(this.min,a[i]); }
                else { this.max = getMax(this.max,a[i]); this.min = getMin(this.min,a[j]); }
          }
     else
     {
           // if P is not small, divide P into sub-problems.
           // Find where to split the set.
           mid = ( i + j )/2;
           // Solve the sub-problems.
           max1=min1=a[mid+1];
           MaxMin( a, i, mid, max, min );
           MaxMin( a, mid+1, j, max1, min1 );
           // Combine the solutions.
           if (this.max < max1) this.max = max1; if (this.min > min1) this.min = min1;
     }
        result[0]=this.max;  result[1]=this.min;
        return result;
    }

    public static int getMax(int i,int j)
    {
        if(i>j) return i;
        else return j;
    }

    public static int getMin(int i,int j)
    {
        if(i>j) return j;
        else return i;
    }
}

OUTPUT:
max-min

Write a program that implements change making solution. Assume that the cashier has currency notes in the denominations Rs. 100, Rs. 50, Rs. 20, Rs. 10, Rs. 5 and Rs. 1 in addition to coins . Program should include a method to input the purchase amount and the amount given by the customer as well as method to output the amount of change and a breakdown by denomination. Apply greedy algorithm at the cahier side that is give less number of coins if sufficient currency of that denomination available.

The change-making problem addresses the following question: how can a given amount of money be made with the least number of coins of given denominations?

It can be solved by dynamic  dynamic programming or greedy approach.we will see an example of solving making change problem using greedy approach.

So,lets see one example of making change problem;

Write a program that implements change making solution. Assume that the cashier has currency notes in the denominations Rs. 100, Rs. 50, Rs. 20, Rs. 10, Rs. 5 and Rs. 1 in addition to coins . Program should include a method to input the purchase amount and the amount given by the customer as well as method to output the amount of change and a breakdown by denomination. Apply greedy algorithm at the cahier side that is give less number of coins if sufficient currency of that denomination available.

 

import java.util.Scanner;
 
public class Change {
	private int[] denom;
	Change( int[] denom) {	
		this.denom = denom;
	}
	void giveChange(int changeRs) {	
		System.out.println("\nChange for " + changeRs + " in Rs " + ":");
		for(int i = 0; i < denom.length; ++i) { int nb = changeRs / denom[i]; if(nb > 0) 
				System.out.println(nb + " " + denom[i]);
			changeRs %= denom[i]; 
		}
	}
	public static void main(String[] args) { 
                 int[] Rs = {100,50,20,10,5,1};  
                Scanner input=new Scanner(System.in);
                System.out.println("Enter the purchase amount : ");
                int purchaseAmount=input.nextInt();
                System.out.println("Enter the amount given by customer : ");
                int AmountGivenByCusto=input.nextInt();
                if(AmountGivenByCusto<purchaseAmount){
                    System.out.println("Sorry! you paid less than purchase amount!  ");                    
                }else
{
                int result=AmountGivenByCusto-purchaseAmount;
		Change change1 = new Change( Rs);
		change1.giveChange(result);
                }			
	}
}

OUTPUT:

change

Write a program to determine whether or not a character string has an unmatched parentheses. Use a stack.

The Question is what is parentheses ?Answer is very simple that parentheses also called bracket. either of a pair of characters, ( ), used to enclose such a phrase or as a sign of aggregation in mathematical or logical expressions.

lets Write a program to determine whether or not a character string has an unmatched parentheses using a stack in java :

 

import java.io.IOException;


public class BracketChecker {
  private String input;

  public BracketChecker(String in) {
    input = in;
  }

  public void check() {
    int stackSize = input.length(); 
    Stack theStack = new Stack(stackSize); 

    for (int j = 0; j < input.length(); j++)
    {
      char ch = input.charAt(j);
      switch (ch) {
      case '{': // opening symbols
      case '[':
      case '(':
        theStack.push(ch); // push them
        break;

      case '}': // closing symbols
      case ']':
      case ')':
        if (!theStack.isEmpty()) // if stack not empty,
        {
          char chx = theStack.pop(); // pop and check
          if ((ch == '}' && chx != '{') || (ch == ']' && chx != '[')
              || (ch == ')' && chx != '('))
            System.out.println("Error: " + ch + " at " + j);
        } else
          
          System.out.println("Error: " + ch + " at " + j);
        break;
      default: // no action on other characters
        break;
      }
    }
    if (!theStack.isEmpty())
      System.out.println("Error: missing right delimiter");
  }

  public static void main(String[] args) throws IOException {
    String input = "{computer {algoritham}";
    BracketChecker theChecker = new BracketChecker(input);
    theChecker.check(); 
  }

}
class Stack {
  private int maxSize;

  private char[] stackArray;

  private int top;

  public Stack(int max) {
    maxSize = max;
    stackArray = new char[maxSize];
    top = -1;
  }

  public void push(char j) {
    stackArray[++top] = j;
  }

  public char pop() {
    return stackArray[top--];
  }

  public char peek() {
    return stackArray[top];
  }

  public boolean isEmpty() {
    return (top == -1);
  }
}

OUTPUT:

para

The array a[0:9]=[4,2,6,7,1,0,9,8,5,3] is to be sorted using insertion sort.

First we understand what is insertion sort,Insertion sort is a simple sorting algorithm that builds the final sorted list(or array) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
It always maintains a sorted sublist in the lower positions of the list. Each new item is then “inserted” back into the previous sublist such that the sorted sublist is one item larger.

now,Lets implement insertion sort in java.

public class MyInsertionSort {
 
    public static void main(String[] args) {
         
        int[] input = {4,2,6,7,1,0,9,8,5,3};
        insertionSort(input);
    }
     
    private static void printNumbers(int[] input) {
         
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
    }
 
    public static void insertionSort(int array[]) {
        int n = array.length;
        for (int j = 1; j < n; j++) { int key = array[j]; int i = j-1; while ( (i > -1) && ( array [i] > key ) ) {
                array [i+1] = array [i];
                i--;
            }
            array[i+1] = key;
            printNumbers(array);
        }
    }
}

OUTPUT:
insert

Write a recursive and nonrecursive function to compute n factorial And Java program to compute n factorial

The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, The value of 0! is 1, 2! is 2, 3! is 6 etc.

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem.
Function to compute n factorial using recursive method :

public int Factorial(int n)
{
	if (n == 0)
		return 1;
	else
		return n * Factorial(n-1);
}

 

now,lets write a java program to find factorial of given number using recursive method :

import java.util.Scanner;
class FactorialDemo{
   public static void main(String args[]){
    
      Scanner scanner = new Scanner(System.in);
      System.out.println("Enter the number:");
      
      int num = scanner.nextInt();
      
      int factorial = fact(num);
      System.out.println("Factorial of entered number is: "+factorial);
   }
   static int fact(int n)
   {
       int output;
       if(n==1){
         return 1;
       }
       //Recursion: Function calling itself!!
       output = fact(n-1)* n;
       return output;
   }
}

OUTPUT :
fact

so,our next question is how can we  find factorial of given number using nonrecursive method or we can say it Iterative method.

here is Function to compute n factorial using non-recursive method :

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;

  return fact;

}

 

now,lets write a java program to find factorial of given number using nonrecursive method.

 

import java.util.Scanner;

public class Factorial {

   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       System.out.print("Enter the number: ");
       int n = scanner.nextInt();
       int result = factorial(n);
       System.out.println("The factorial of " + n + " is " + result);
   }

   public static int factorial(int n) {
       int result = 1;
       for (int i = 1; i <= n; i++) {
           result = result * i;
       }
       return result;
   }
}

OUTPUT:
fact2

JavaScript Introduction

What is JavaScript ?

JavaScript could be the world’s most widely used coding language. It is the language for HTML and the net, for hosts, PCs, laptops, tablets, intelligent devices, and more.

JavaScript Language :

A scripting language is really a lightweight development language.
JavaScript is development code that can be put in to HTML pages.
JavaScript put in to HTML pages, could be accomplished by all contemporary web browsers.
JavaScript is easy to learn.

JavaScript: Writing Into HTML Output

JavaScript: Reacting to Events

The alert() function is very little utilized in JavaScript, but it’s frequently quite useful for trying out code.
The onclick function is only one of the numerous HTML functions.