Sunday, November 19, 2017

Re-Engineering the Internet for Real Net Neutrality

"Internet needs not just regulation but also accurate and efficient metering of traffic to make it cost inefficient for piracy/human rights violators and hackers. Let charges for every packet going around in the internet be made. Many corporations will have to close down what with excessive charges for their automatic updates. Internet is heavily tilted in favor of the corporations. We(consumers) pay for viewing the ads(data costs). We have to bear all expenses no matter the benefiting party."

This was my comment in one of the sites where net neutrality was being discussed. In traditional transactions the benefiting party pays for the goods and services. In the internet it is always the user who pays no matter what he does with it. A model for charging for services where the real user pays and the real provider of service gets the money is needed.

Many users on the internet generate content and they are never credited for the data or talent they exhibit. Be it bloggers or You tube channels. A massive reorganization of the internet where charges for the network traffic are made based on the duration or volume of traffic carried could be tried. Every packet that goes around the internet should potentially be charged some money to someone just as a car pays for the toll on the roads.


Uniqueness and provenance should be the only guiding factors for people to lay claim to copyrights. Data compression alone will not reduce bandwidth requirements from network traffic and radical new ways of metering connections which is inclusive of people left out of the internet should be made to bridge the digital divide.

Internet is turning out to be a mega scam where mega corporations with ad servers and SEO companies are having a field day at the cost of the talent/copyright holder.

Your comments are welcome!

Sunday, April 2, 2017

Numerical Methods Problems

Some numerical methods problems from B S Grewal...

Regula - falsi
1) Find a real root of the equation x3-2x-5=0 by the method of false position correct to three decimal places.
2) Find the root of the equation cos x=xex using regular-falsi method correct to four decimal places.
3) Find the real root of the equation x log 10 x = 1.2 by regula-falsi method correct upto four decimal places.
4) Use the method of false position, to find the fourth root of 32 correct upto three decimal places.
5) Using regula-falsi method, find the real root of the following equations correct to three decimal places:
i) xex=2                 ii) cos x=3x-1      iii) xex=sinx    iv) x tanx=-1            v) 2x-logx=7       vi) 3x+sinx=ex
6) Find the fourth root of 12 correct to three decimal places by interpolation method(regula falsi)
7) Locate the root of f(x) = x10 -1=0 between 0 and 1.3 using method of false position.
Newton – Raphson
1) Find the positive root of x4-x=10 correct to three decimal places using newton-raphson method.
2) Find by newton’s method, the real root of the equation 3x=cosx+1 correct to four decimal places.
3) Using Newton’s iterative method, find the real root of x log 10 x = 1.2 correct to five decimal places.
4) Find by newton-raphson method, a root of the following equations correct upto 3 decimal places.
i) x3-3x+1=0     ii) x3-2x-5=0      iii) x3-5x+3=0       iv) 3x3-9x2+8=0
5) Using newton’s iterative method, find a root of the following equations correct to 4 decimal places:
i) x4+x3-7x2-x+5=0 which lies between 2 and 3.
ii) x5 – 5 x2 +3=0
6) Find the negative root of equation x3 -21x +3500=0 correct to 2 decimal places by newton’s method.
7) Using Newton-Raphson method, find a root of the following equations correct to 3 decimal places:
i) x2+4sinx=0
ii) x sinx+cosx=0
iii) ex=x3+cos25x which is near 4.5

iv) x log 10 x=12.34 start with x0=4.5
v) cosx = x ex
vi) 10x+x-4=0
8) use newton’s method to find the smallest root of the equation ex sinx=1 to four decimal places.
9) Develop an algorithm using N.R method, to find the fourth root of a positive number N and hence find .(fourth root of 32).

10) evaluate the following(correct to 3 decimal places) by using newton-raphson method.
i) 1/18                   ii) 1/ (square root of 15)             iii) (28)-1/4

11) State and explain the newton-raphson method to find the roots of a differentiable equation.


Gauss Elimination Method:
1) Apply the gauss elimination method to solve the equations x+4y-z=-5; x+y-6z=-12; 3x-y-z=4
2)Solve 10x-7y+3z+5u=6; -6x+8y-z-4u=5; 3x+y+4y+11u=2; 5x-9y-2z+4u=7 by gauss elimination.
3) Using gauss elimination method, solve the equations x+2y+3z-u=10, 2x+3y-3z-u=1, 2x-y+2z+3u=7, 3x+2y-4z+3u=2.
4) Solve the following equations by gauss elimination method:
i) x + y + z=9; 2x - 3y + 4z = 13; 3x + 4y + 5z = 40
ii) 2x + 2y + z = 12; 3x + 2y + 2z = 8; 5x + 10y -8z =10
iii) 2x – y + 3z = 9; x + y + z = 6; x – y + z=2
iv) 2x1 + 4x2 + x3 = 3; 3x1 + 2x2 – 2x3= -2; x1 – x2 + x3 = 6
v) 5x1 + x2 + x3 + x4 = 4; x1 + 7x2 + x3 + x4 = 12; x1 + x2 + 6x3 + x4 = -5; x1 + x2 + x3 + 4x4= -6

Gauss-jordan method:
1) Apply Gauss-jordan method to solve the equations
 x + y + z=9; 2x - 3y + 4z = 13; 3x + 4y + 5z = 40
2) Solve the equations 10x-7y+3z+5u=6;
                                                -6x+8y-z-4u=5;
                                                3x+y+4z+11u=2;
                                                5x-9y-2z+4u=7

3) solve the following equations by Gauss-Jordan Method:
i) 2x+5y+7z=52; 2x+y-z=0; x+y+z=9
ii) 2x – 3y +z=-1; x +4y +5z=25; 3x-4y+z=2
iii) x + y+ z=9; 2x+y-z=0; 2x+5y+7z=52
iv) x + 3y + 3z=16; x + 4y + 3z=18; x + 3y + 4z=19
v) 2x1+x2+5x3+x4=5; x1+x2-3x3+4x4=-1
    3x1+6x2-2x3+x4=8; 2x1+2x2+2x3-3x4=2

LU decomposition:
1) Solve the following equations by factorization method:
i) 2x+3y+z=9; x+2y+3z=6; 3x+y+2z=8
ii) 10x+y+z=12; 2x+10y+z=13; 2x+2y+10z=14
iii) 10x+y+2z=13; 3x+10y+z=14; 2x+3y+10z=15
iv) 2x1-x2+x3=-1; 2x2-x3+x4=1; x1+2x3-x4=-1; x1+x2+2x4=3

Iterative methods:
Jacobi’s Iteration:
1) Solve by Jacobi’s iteration method, the equations
20x+y-2z=17;
3x+20y-z=-18;
2x-3y+20z=25
2) Solve by jacobi’s iteration method, the equations 10x + y – z=11.19
                                                                                                       x+10y+z=28.08;
                                                                                                      -x+y+10z=35.61
3) Solve the equations:
10x1-2x2-x3-x4=3;
-2x1+10x2-x3-x4=15;
-x1-x2+10x3-2x4=27;
-x1-x2-2x3+10x4=-9

4) Solve by jacobi’s method, the equations: 5x-y+z=10;
                                                                                     2x+4y=12;
                                                                                     x+y+5z=-1 starting with the solution{2,3,0}

5) Solve by jacobi’s method the equations:
13x + 5y-3z+u=18;
2x+12y+z-4u=13;
x-4y+10z+u=29;
2x+y-3z+9u=31;

Gauss-Seidel Method:
1) Apply Gauss-Seidel iteration method to solve the equations 20x+y-2z=17
3x+20y-z=-18; 2x-3y+20z=25

2) Solve the equations 27x+6y-z=85;
                                                x+y+54z=110;
                                                6x+15y+2z=72;

3) Apply Gauss-Seidel iteration method to solve the equations:
10x1-2x2-x3-x4=3;
-2x1+10x2-x3-x4=15;
-x1-x2+10x3+2x4=27;
-x1-x2-2x3+10x4=-9

4) Solve the following equations by Gauss-seidel method:
i) 2x+y+6z=9; 8x+3y+2z=13; x+5y+z=7
ii) 28x+4y-z=32; x+3y+10z=24; 2x+17y+4z=35;
iii) 10x+y+z=12; 2x+10y+z=13; 2x+2y+10z=14;
iv) 7x1+52x2+13x3=104; 83x1+11x2-4x3=95; 3x1+8x2+29x3=71

v) 3x1-0.1x2-0.2x3=7.85; 0.1x1+7x2-0.3x3=-19.3; 0.3x1-0.2x2+10x3=71.4

Saturday, April 1, 2017

A Mathematician's Lament

A Mathematician’s Lament
by Paul Lockhart
A musician wakes from a terrible nightmare.  In his dream he finds himself in a society where music education has been made mandatory.  “We are helping our students become more competitive in an increasingly sound-filled world.”  Educators, school systems, and the state are put in charge of this vital project.  Studies are commissioned, committees are formed, and decisions are made— all without the advice or participation of a single working musician or composer.
Since musicians are known to set down their ideas in the form of sheet music, these curious black dots and lines must constitute the “language of music.”  It is imperative that students become fluent in this language if they are to attain any degree of musical competence; indeed, it would be ludicrous to expect a child to sing a song or play an instrument without having a thorough grounding in music notation and theory.  Playing and listening to music, let alone composing an original piece, are considered very advanced topics and are generally put off until college, and more often graduate school. 
As for the primary and secondary schools, their mission is to train students to use this language— to jiggle symbols around according to a fixed set of rules:  “Music class is where we take out our staff paper, our teacher puts some notes on the board, and we copy them or transpose them into a different key.  We have to make sure to get the clefs and key signatures right, and our teacher is very picky about making sure we fill in our quarter-notes completely.
One time we had a chromatic scale problem and I did it right, but the teacher gave me no credit because I had the stems pointing the wrong way.”  
In their wisdom, educators soon realize that even very young children can be given this kind of musical instruction.  In fact it is considered quite shameful if one’s third-grader hasn’t completely memorized his circle of fifths.  “I’ll have to get my son a music tutor.  He simply won’t apply himself to his music homework.  He says it’s boring.  He just sits there staring out the window, humming tunes to himself and making up silly songs.”
In the higher grades the pressure is really on.  After all, the students must be prepared for the standardized tests and college admissions exams.  Students must take courses in Scales and Modes, Meter, Harmony, and Counterpoint.  “It’s a lot for them to learn, but later in college when they finally get to hear all this stuff, they’ll really appreciate all the work they did in high school.”  Of course, not many students actually go on to concentrate in music, so only a few will ever get to hear the sounds that the black dots represent.  Nevertheless, it is important that every member of society be able to recognize a modulation or a fugal passage, regardless of the fact that they will never hear one.  “To tell you the truth, most students just aren’t very good at music.
They are bored in class, their skills are terrible, and their homework is barely legible.  Most of them couldn’t care less about how important music is in today’s world; they just want to take the minimum number of music courses and be done with it.  I guess there are just music people and non-music people.  I had this one kid, though, man was she sensational!  Her sheets were impeccable— every note in the right place, perfect calligraphy, sharps, flats, just beautiful. She’s going to make one hell of a musician someday.”

Waking up in a cold sweat, the musician realizes, gratefully, that it was all just a crazy dream.  “Of course!” he reassures himself, “No society would ever reduce such a beautiful and meaningful art form to something so mindless and trivial; no culture could be so cruel to its children as to deprive them of such a natural, satisfying means of human expression.  How absurd!”  

Meanwhile, on the other side of town, a painter has just awakened from a similar nightmare…

I was surprised to find myself in a regular school classroom— no easels, no tubes of paint.  “Oh we don’t actually apply paint until high school,” I was told by the students.  “In seventh grade we mostly study colors and applicators.”  They showed me a worksheet.  On one side were swatches of color with blank spaces next to them.  They were told to write in the names.  “I like painting,” one of them remarked, “they tell me what to do and I do it.  It’s easy!” 
After class I spoke with the teacher.  “So your students don’t actually do any painting?” I asked.  “Well, next year they take Pre-Paint-by-Numbers.  That prepares them for the main Paint-by-Numbers sequence in high school.  So they’ll get to use what they’ve learned here and apply it to real-life painting situations— dipping the brush into paint, wiping it off, stuff like that.
Of course we track our students by ability.  The really excellent painters— the ones who know their colors and brushes backwards and forwards— they get to the actual painting a little sooner, and some of them even take the Advanced Placement classes for college credit.  But mostly we’re just trying to give these kids a good foundation in what painting is all about, so when they get out there in the real world and paint their kitchen they don’t make a total mess of it.”

“Um, these high school classes you mentioned…”

“You mean Paint-by-Numbers?  We’re seeing much higher enrollments lately.  I think it’s mostly coming from parents wanting to make sure their kid gets into a good college.  Nothing looks better than Advanced Paint-by-Numbers on a high school transcript.”looks better than Advanced Paint-by-Numbers on a high school transcript.”

“Why do colleges care if you can fill in numbered regions with the corresponding color?”

“Oh, well, you know, it shows clear-headed logical thinking.  And of course if a student is planning to major in one of the visual sciences, like fashion or interior decorating, then it’s really a good idea to get your painting requirements out of the way in high school.”
“I see.  And when do students get to paint freely, on a blank canvas?”
“You sound like one of my professors!  They were always going on about expressing yourself and your feelings and things like that—really way-out-there abstract stuff.  I’ve got a degree in Painting myself, but I’ve never really worked much with blank canvasses.  I just use the Paint-by-Numbers kits supplied by the school board.”


Sadly, our present system of mathematics education is precisely this kind of nightmare.  In fact, if I had to design a mechanism for the express purpose of destroying a child’s natural curiosity and love of pattern-making, I couldn’t possibly do as good a job as is currently being done— I simply wouldn’t have the imagination to come up with the kind of senseless, soul-crushing ideas that constitute contemporary mathematics education.

Sunday, March 19, 2017

Kolmogorov Complexity

Any random string has inherent complexity and taking the algorithmic complexity approach it is described by kolmogorov complexity. The random string 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)

Sunday, January 15, 2017

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