Kolmogorov Complexity

Any random string has inherent complexity and taking the algorithmic complexity approach it is described by kolmogorov complexity. The random string w is said to have complexity of K(w) which is given as the length of the shortest program that generates w.

If a program generates a string w has length less than w then kolmogorov complexity of the string is the length of that program. 

We usually have patterns of data taken from our surroundings. Complex processes of physics, chemistry and optics are at play in generation of the patterns that we see around us. Suppose we set out to catalog every pattern of strings generated by computers on the internet. With such a big data its mining would take much time under ordinary circumstances.
Just an image of 100 pixels cross 100 pixels with 8 bits per pixel depth would produce 2 power 80,000 different image combinations.

Research unto death

Knowledge gaps imply researchers from underprivileged backgrounds have to struggle much more. "As the infusion of mass media information into a social system increases, higher socioeconomic status segments tend to acquire this information faster than lower socioeconomic-status population segments so that the gap in knowledge between the two tends to increase rather than decrease"...(Source: google)

The thing is productivity of research and its ultimate end use are a function of the economy. After all the low hanging fruits have been plucked, it would seem there would come a slow death of research. The law of diminishing returns would dictate that this science, medicine and engineering thing would stop bearing fruits. Wells would turn dry. Once that happens and in a stagnant economy the dominant discourse would move from unlimited opportunities and synergy to "Sharing a pie" or a "zero sum game". Once that happens the dominant economic discourse would turn more leftist.

To strike at the roots of economic imbalance we have to have equal opportunities for all. 

Several people would just be required to study and be knowledgeable enough to predict the future. Professors just have one thing to do. Research and then some more research. (I thought a few random thoughts streaking through my mind when posted in this user generated content post would enrich the internet)

Boyer Moore algorithm

/**
 ** Java Program to implement Boyer Moore Algorithm
 **/
package AdvancedAlgo;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

/** Class BoyerMoore **/
public class BoyerMoore
{
    /** function findPattern **/
    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);
    }
    /** Function to calculate index of pattern substring **/
    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 += pattern.length - j; // For naive method
              i += Math.max(offsetTable[pattern.length - 1 - j], charTable[text[i]]);
        }
        return -1;
      }
      /** Makes the jump table based on the mismatched character information **/
      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;
      }
      /** Makes the jump table based on the scan offset which mismatch occurs. **/
      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;
    }
    /** function to check if needle[p:end] a prefix of pattern **/
    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;
    }
    /** function to returns the maximum length of the substring ends at p and is a suffix **/
    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;
    }
    /** Main Function **/
    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);    
    }
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Input/Output:

Boyer Moore Algorithm Test


Enter Text

hello how are you

Enter Pattern

are
Pattern found at position : 10

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