Miller Rabin Primality Testing

Primality Testing:

/**Java Program to Implement Miller Rabin Primality Test Algorithm**/

package AdvancedAlgo;
import java.util.Scanner;
import java.util.Random;
import java.math.BigInteger;

/** Class MillerRabin **/
public class MillerRabin
{
    /** Function to check if prime or not **/
    public boolean isPrime(long n, int iteration)
    {
       /** base case **/
       if (n == 0 || n == 1)
            return false;
        /** base case - 2 is prime **/
        if (n == 2)
           return true;
       /** an even number other than 2 is composite **/
       if (n % 2 == 0)
           return false;
       long s = n - 1;
       while (s % 2 == 0)
           s /= 2;
       Random rand = new Random();
       for (int i = 0; i < iteration; i++)
       {
           long r = Math.abs(rand.nextLong());          
           long a = r % (n - 1) + 1, temp = s;
           long mod = modPow(a, temp, n);
           while (temp != n - 1 && mod != 1 && mod != n - 1)
           {
               mod = mulMod(mod, mod, n);
               temp *= 2;
           }
           if (mod != n - 1 && temp % 2 == 0)
                return false;
        }
        return true;      
    }

    /** Function to calculate (a ^ b) % c **/
    public long modPow(long a, long b, long c)
    {
       long res = 1;
       for (int i = 0; i < b; i++)
       {
           res *= a;
           res %= c;
       }
       return res % c;
    }

   /** Function to calculate (a * b) % c **/
   public long mulMod(long a, long b, long mod)
   {
       return BigInteger.valueOf(a).multiply(BigInteger.valueOf(b)).mod(BigInteger.valueOf(mod)).longValue();
   }

   /** Main function **/
   public static void main (String[] args)
   {
       Scanner scan = new Scanner(System.in);
       System.out.println("Miller Rabin Primality Algorithm Test\n");

       /** Make an object of MillerRabin class **/
       MillerRabin mr = new MillerRabin();

      /** Accept number **/
       System.out.println("Enter number\n");
       long num = scan.nextLong();

       /** Accept number of iterations **/
       System.out.println("\nEnter number of iterations");

       int k = scan.nextInt();
       /** check if prime **/
       boolean prime = mr.isPrime(num, k);
       if (prime)
            System.out.println("\n"+ num +" is prime");
       else
            System.out.println("\n"+ num +" is composite");
    }
}


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Input/Output:

Miller Rabin Primality Algorithm Test

Enter number

65537

Enter number of iterations
100

65537 is prime

Rabin Karp pattern Matching Algorithm

/**
 ** Java Program to Implement Rabin Karp Pattern 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; /** String Pattern **/
    private long patHash; /** pattern hash value **/
    private int M;   /** pattern length **/
    private long Q; /** Large prime **/
    private int R; /** radix **/
    private long RM; /** R^(M-1) % Q **/
    private int KeyCount; /** key operation counter **/

    public RabinKarp(String txt, String pat) /** Constructor **/
    {
        this.pat = pat;
        R = 256;
        M = pat.length();
        Q = longRandomPrime();
        KeyCount = 0;

        /** precompute R^(M-1) % Q for use in removing leading digit **/
        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);
        System.out.println("\nNo of comparisons : " + KeyCount );
        }
    }

    /** Compute hash **/
    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;
    }

    /** Funtion check **/
    private boolean check(String txt, int i)
    {
        for (int j = 0; j < M; j++){
        KeyCount++;
        if (pat.charAt(j) != txt.charAt(i + j))
                return false;
        }
        return true;
    }

    /** Funtion to check for exact match**/
    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)) /** check for match at start **/
            return 0;

        /** check for hash match. if hash match then check for exact match**/
        for (int i = M; i < N; i++)
        {
            // Remove leading digit, add trailing digit, check for match.
            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
            txtHash = (txtHash * R + txt.charAt(i)) % Q;
            // match
            int offset = i - M + 1;
            if ((patHash == txtHash) && check(txt, offset))
                return offset;
        }

        return -1; /** no match **/
    }

    /** generate a random 31 bit prime **/
    private static long longRandomPrime()
    {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }

    /** Main Function **/
    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);
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Input/Output:

Rabin Karp Algorithm Test

Enter Text

Hello How are you

Enter Pattern

are

Results : 

Pattern found at position : 10

No of comparisons : 3

(Please note: WTF   #$@%!^^ Just 3)

Knuth Morris Pratt Algorithm for Pattern Matching

/**
 ** Java Program to implement Knuth Morris Pratt Algorithm
 **/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class KnuthMorrisPratt
{
    private int[] failure; /** Failure array **/
    private int KeyCount; /** key operation counter **/

    public KnuthMorrisPratt(String text, String pat) /** Constructor **/
    {
        KeyCount = 0;
        failure = new int[pat.length()]; /** pre construct failure array for a pattern **/
        fail(pat);
        int pos = posMatch(text, pat); /** find match **/
        if (pos == -1)
            System.out.println("\nNo match found");
        else {
        System.out.println("\nMatch found at index "+ pos);
        System.out.println("\nNo of comparisons : " + KeyCount );
        }
    }

    /** Failure function for a pattern **/
    private void fail(String pat)
    {
        int n = pat.length();
        failure[0] = -1;
        for (int j = 1; j < n; j++)
        {
            int i = failure[j - 1];
            //KeyCount++;
            while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0){
            i = failure[i];
            //KeyCount++;
            }


            if (pat.charAt(j) == pat.charAt(i + 1))
                failure[j] = i + 1;
            else
                failure[j] = -1;
        }
    }

    /** Function to find match for a pattern **/
    private int posMatch(String text, String pat)
    {
        int i = 0, j = 0;
        int lens = text.length();
        int lenp = pat.length();
        while (i < lens && j < lenp)
        {
        KeyCount++;
            if (text.charAt(i) == pat.charAt(j))
            {
                i++;
                j++;
            }
            else if (j == 0)
                i++;
            else
                j = failure[j - 1] + 1;
        }
        return ((j == lenp) ? (i - lenp) : -1);
    }

    /** Main Function **/
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Knuth Morris Pratt Test\n");
        System.out.println("\nEnter Text\n");
        String text = br.readLine();
        System.out.println("\nEnter Pattern\n");
        String pattern = br.readLine();
        KnuthMorrisPratt kmp = new KnuthMorrisPratt(text, pattern);
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Input-Output:

Knuth Morris Pratt Test

Enter Text

hello how are you

Enter Pattern

are

Match found at index 10

No of comparisons : 13

Pattern Matching using Deterministic Finite Automaton

Pattern Matching using DFA in Java:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
package AdvancedAlgo;
import java.util.Scanner;
public class DFA {
public static final int NO_OF_CHARS = 256;
public static int getNextState(char[] pat, int M, int state, int x) {
/* If the character c is same as next character in pattern,then simply increment state*/
if (state < M && x == pat[state])
return state + 1;
int ns, i;

/* ns stores the result which is next state ns finally contains the longest prefix which is
* also suffix in "pat[0..state-1]c". Start from the largest possible value and stop when
* you find a prefix which is also suffix
**/
for (ns = state; ns > 0; ns--) {
if (pat[ns - 1] == x) {
for (i = 0; i < ns - 1; i++) {
if (pat[i] != pat[state - ns + 1 + i])
break;
}
if (i == ns - 1)
return ns;
}
}
return 0;
}

/*
* This function builds the TF table which represents Finite Automata for a
* given pattern
*/
public static void computeTF(char[] pat, int M, int[][] TF) {
int state, x;

for (state = 0; state <= M; ++state)
for (x = 0; x < NO_OF_CHARS; ++x)
TF[state][x] = getNextState(pat, M, state, x);
}

/*
* Prints all occurrences of pat in txt
*/
public static void search(char[] pat, char[] txt) {
int M = pat.length;
int N = txt.length;
int[][] TF = new int[M + 1][NO_OF_CHARS];
computeTF(pat, M, TF);

// Process txt over FA.
int i, state = 0;
for (i = 0; i < N; i++) {
state = TF[state][txt[i]];
if (state == M) {
System.out.print(" \npattern found at position: " + (i - M + 1));
}
}
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the main string: ");
String textStr = sc.nextLine();
System.out.println("Enter the pattern string: ");
String pattern = sc.nextLine();

search(pattern.toCharArray(), textStr.toCharArray());
sc.close();
}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Input/Output:

Enter the main string:
abcdefghijklmnopqrstuvwxy
Enter the pattern string:
xy

pattern found at position: 23

Bellman Ford Algorithm

Bellman Ford Algorithm
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

package AdvancedAlgo;
import java.io.*;
import java.util.Scanner;

public class BellmanFord
{
    private int distances[ ];
    private int numberofvertices;
    public static final int MAX_VALUE = 999;
    private int source;
    private int adjacencymatrix[ ][ ];

    public BellmanFord( ) throws IOException{
    Scanner scanner = new Scanner(System.in);

        System.out.println("Enter the number of vertices");
        numberofvertices = scanner.nextInt();
        distances = new int[numberofvertices + 1];

        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();
        BellmanFordEvaluation( );
        scanner.close();
    }

    public void BellmanFordEvaluation( ){
        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 edge cycle");
                            return;
                            }

        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) throws IOException {
        BellmanFord bellmanford = new BellmanFord( );
    }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Input/Output:

Enter the number of vertices
5
Enter the adjacency matrix
0 6 999 999 7
999 0 5 -4 8
999 -2 0 999 999
2 999 7 0 999
0 999 -3 9 0
Enter the source vertex
1
distance of source  1 to 1 is 0
distance of source  1 to 2 is 2
distance of source  1 to 3 is 4
distance of source  1 to 4 is -2
distance of source  1 to 5 is 7

Naive String Matching

This Algorithm/Code in Java performs naive string matching:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

package AdvancedAlgo;
import java.util.Scanner;

public class NaiveMethod {
private final int BASE;
private int[ ] occurrence;
private String pattern;
public int KeyCount; /** key operation counter **/

public NaiveMethod(String pattern) {
this.BASE = 256;
this.pattern = pattern;
KeyCount = 0;
occurrence = new int[BASE];

for (int c = 0; c < BASE; c++)
occurrence[c] = -1;
for (int j = 0; j < pattern.length(); j++)
occurrence[pattern.charAt(j)] = j;
}

public int search(String text) {
int n = text.length();
int m = pattern.length();
int skip;
for (int i = 0; i <= n - m; i += skip) {
skip = 0;
for (int j = m - 1; j >= 0; j--) {
KeyCount++;
if (pattern.charAt(j) != text.charAt(i + j)) {
skip = Math.max(1, j - occurrence[text.charAt(i + j)]);
break;
}
}
if (skip == 0)
return i;
}
return n;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the main string: ");
String text = sc.nextLine();
System.out.print("Enter the string to be searched: ");
String pattern = sc.nextLine();
NaiveMethod nsm = new NaiveMethod(pattern);
int first_occur_position = nsm.search(text);
System.out.println("The text '" + pattern + "' is first found after the " + first_occur_position
+ " position.");
System.out.println("\nNo of comparisons : " + nsm.KeyCount );
sc.close();
}
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Input / Output:

Enter the main string: Hello How are You
Enter the string to be searched: are
The text 'are' is first found after the 10 position.

No of comparisons : 7

In India, English is mandatory to be a Researcher

Worst of all, you are considered uncivil if you speak native language. People are turning en-mass English speakers in the hope that someday they will land in the Americas. Researchers without English knowledge stand no chance since all literature is published in foreign language. Under such circumstances how do you research, when you can't survey the literature nor write in any journal in your mother tongue.
Most Indian schools teach you in mother tongue till a couple of years and then switch over to English. Many students drop out due to economic reasons but many are not able to pick up English skills and they too drop out of school.
Hence inability to pick up English becomes a big reason why many bright students are excluded from the education system. India is home to more than a thousand dialects. Out of them many do not have a script. With only 28 states each of which teach in one language only, speakers of other languages are left to accept the language of their home state.
Diversity in languages and cultures is neither celebrated nor respected.