Thursday, 24 October 2013

Java Producer-Consumer example using wait and notify

An example in java for Producer-Consumer problem using wait() and notify() :

public class Threads {
    /**
     * @param args
     * @author vikky.agrawal
     */

    public static void main(String args[]) {

        Semaphore mutex = new Semaphore();

        Producer producer = new Producer(mutex);
        Consumer consumer = new Consumer(mutex);

        System.out.println("Main starts");

        producer.start();
        consumer.start();

        try {
            consumer.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Main Stop");
    }
}

class Consumer extends Thread {

    Semaphore mutex;

    Consumer(Semaphore mutex) {
        super("Consumer");
        this.mutex = mutex;
    }

    @Override
    public void run() {

        for (int i = 0; i < 50; i++) {
          
            try {
                sleep(1000);
                mutex.down();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

    }

}

class Producer extends Thread {

    Semaphore mutex;

    Producer(Semaphore mutex) {
        super("producer");
        this.mutex = mutex;

    }
  
    @Override
    public void run() {

        for (int i = 0; i < 100; i++) {          
            mutex.up();          
            try {
                sleep(10);
            } catch (InterruptedException e) {
            }

        }

    }
}

class Semaphore {

    static int value = 0;
    boolean available = false;
  
    public synchronized void down() {
        while (!available) {
            try {
              
                wait();
              
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //System.out.println("Consumer woke up from waiting");
        }
        value--;
        System.out.println("Consumed now value : "+value);
        available = false;
        notify();      
    }

    public synchronized void up() {

        while (available) {
            try {
                wait();
                //System.out.println("Producer Got a notification and available is now: "+available);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            //System.out.println("Producer woke up from waiting");
        }
        value++;
        System.out.println("Produced now value :"+ value);
        available = true;
        notify();      
    }
}

Wednesday, 23 October 2013

How HashMap works in Java.

How HashMap works in Java.

HashMap works on the principle of hashing. A HashMap stores keys and associated values.
Using hashcode keys are assigned bucket and both key and value gets stored in it.
  • HashMap allows null key as well as null value(s).
  • HashMap implementation ensures that its array length is always equal to at least max( size, capacity ) / load_factor. Default load factor for HashMap is 0.75 and default capacity is 16. So, the default (new HashMap<>()) size of array of entries is 16 / 0.75 = 21.33 ~ 22. 
  • In case this size fills HashMap doubles it's size and rehashes all the entries.
  • Equals method implies Hashcode i.e.  equals() => hashcode().
  • public V put(K key, V value)
    Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced. 
How get() method works in HashMap?
Using key as input HashMap calculates its hashcode() and then locates the key and its associated value in bucket.

Connecting question is: What if two keys have same hashcode()?
Two keys having same hashcode() will land in same bucket.
So if you know Hashing it's a matter of collision resolution, in case of a collision in HashMap, key-value pairs are stored in a LinkedList, so once there is a collision one needs to locate the bucket using hashcode() and then using equals() method locate key and return its associated value.

hashcode() => locate bucket => equals() => identify key based on equals() and return its associated value.


Code for testing:

import java.util.HashMap;

public class HashMapImpl {

    /**
     * @param args
     * @author vikky.agrawal
     */
    public static void main(String[] args) {
        HashMap<Integer, String> map=new HashMap<Integer, String>();
       
        map.put(1, "Hello");
        map.put(2, "Hi");
        map.put(3, "Green");
        map.put(1,"Duplicate");      
       
        System.out.println("Last value replaces first : "+map.get(1));
        System.out.println("Will return false : "+map.containsValue("Hello"));       

    }

}





Monday, 14 October 2013

Java program to count prime numbers for a given range.

import java.util.ArrayList;
import java.util.Date;

public class PrimeCount {

    /**
     * @param args
     * @Author Vikky Agrawal
     */
    public static void main(String[] args) {
      
        int input=1000000;
        ArrayList<Integer> prime=new ArrayList<Integer>();      
      
        prime.add(3);
        prime.add(5);
      
        int primes= 3;
      
        //long start=System.currentTimeMillis();
        long startTime = new Date().getTime();

        boolean temp=false;
        for(int i=7; i<=input; i+=2){          
                temp=false;              
                int index=0;
                int j=prime.get(index);
                int sqrt=(int)(Math.floor(Math.sqrt(i)));
                for(; j<=sqrt; ){  
                    int k=i%j;                  
                    if( k == 0){
                        temp=true;
                        break;
                    }
                    j=prime.get(++index);
                }
                if(!temp){  
                    if(i <(input/2)){
                        prime.add(i);
                    }                  
                    primes++;
                }
            }          
      
        long endTime = new Date().getTime();
        long duration = endTime - startTime;

        System.out.println("Time taken is : " + duration+" milliseconds");
        System.out.println("Number of prime count for input : "+input+" is : "+primes);  
                  
    }
}

How I made my android advertisement free.!

To make android device advertisement free, one need to root android device.
There are plenty of guides available on internet to root your device so follow anyone.

Once android is rooted then follow these simple steps:

1. Install fiddler on your computer.(To capture web traffic from android)
    Download it from here: Fiddler 2
    Go to tools fiddler options and select the options as given in figure:
    Accept the notification if any.






2. Install proxydroid from google play and give it super user access.
    Now enter your ip address (using cmd and ipconfig /all) in proxydroid app.
    and then click on enable proxy switch. This will route all the traffic from your android to your system and fiddler will be able to capture it.

3. Now next step could be completed in two ways:
    We need to update hosts file provided inside /system/etc/hosts
  one way is to use adb commands, pull update and then push this file.
 other easy way is to use any root application for android which could transfer files from one location to other.

I am using second approach as it's easy and convenient.

So download File Explorer and also download root access for it.

Once it's operational copy hosts file from /system/etc/hosts to /mnt/sdcard so you can download it to your computer using data cable.

Once hosts file available on computer use all the host address(advertisers which you got from step 2) to redirect to localhost.
A sample hosts file I created and using on my android (contains some adservers URL from adfree application)

# Ad server list for use with hosts files to block ads

127.0.0.1 localhost

# The following lines are desirable for IPv6 capable hosts
::1     ip6-localhost ip6-loopback
fe00::0 ip6-localnet
ff00::0 ip6-mcastprefix
ff02::1 ip6-allnodes
ff02::2 ip6-allrouters
 
127.0.0.1 ads.mopub.com
127.0.0.1 android.bonzai.mobi
127.0.0.1 d.applovin.com
127.0.0.1 a.applovin.com
127.0.0.1 applovin.com
127.0.0.1 netspiderads.indiatimes.com
127.0.0.1 netspiderads2.indiatimes.com
127.0.0.1 netspiderads3.indiatimes.com
127.0.0.1 media.admob.com
 # 127.0.0.1 your advertiser hosts to block


Add your hosts in above line and remove comment.

Now we need to push this file on android, so copy the same on your sdcrad using data cable and then using file explorer with root access replace this file at /system/etc/hosts.

Switch off and restart your phone.

Now most of the applications will be adfree.
Enjoy. :)


Note:
Android should be rooted for the whole process and proper care should be taken.
These are my views and no responsibility taken for any harm or anything wrong happens while following this process.

Tuesday, 2 July 2013

Pascle Triangle in Java

public class PascalTriangle {

int arr[];
private int N;

public static void main(String arg[]) {
PascalTriangle obj = new PascalTriangle(5);
int output[]=obj.fillUsingPermutation();
for(int a :output){
System.out.println(a);
}
}

public PascalTriangle(int N) {
this.N=N;
this.arr = new int[this.getSize(N)];
}

private int getSize(int N) {
int i = 0;
while (N > 0) {
i += N--;
}
return i;
}

private int[] fillUsingPermutation() {
int k=0 ;
for (int n = 0; n < N && k<arr.length; n++) {
int r=0;
while(r <= n){
arr[k]= fact(n)/(fact(r)*fact(n-r));
r++;
k++;
}
}

return this.arr;
}

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

}

Monday, 31 December 2012

Algorithms- Getting started

To learn the analysis of algorithms and to dive in the study of complexity for algorithms few mathematical concepts are required and used in almost all cases.
I am presenting few concepts in simple manner, so a beginner  can grasp it easily and use it in further study of algorithms.
Asymptotic notations:
Asymptotic notations


Big O notation  (middle image in above figure):
O(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}.
It specifies that function gives a upper bound on the complexity of the algorithm and it's the highest value that an algorithm could achieve and not depends on any particular condition, whatever is the input its the highest bound on the time.
whenever we write f(n) = O(g(n)) then f(n) is upper bounded by g(n), it means g(n) is having more value than f(n) or in other words{though not technically correct, we can write value of f(n)<= g(n)}.

Θ-notation :(First image in above fig.)
Θ(g(n)) = {f(n) : there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}.
function f(n) is sandwiched between g(n) for any two arbitrary constants c1 and c2 such that for any value(eg c1=1/2) f(n) is smaller than g(n) as well as for any other value (eg c2=3/2) f(n) is greater than g(n).
Θ notation is more stronger than O notation and we can write Θ subset of O.
The definition of Θ(g(n)) requires that every member f(n) Θ(g(n)) be asymptotically non-negative, that is, that f(n) be non-negative whenever n is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large n.) Basically it is all related to set theory and we denote each set as a set of functions and complexity is based only for positive functions only.

Ω-notation: (Last image in above fig.) :
Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ no}.
it means function f(n) is greater than g(n) for a sufficient value of constant c.

Few facts:
  • The constants(c1,c2 etc)  mentioned in each case should be only numerical constants and should not be any exponential or any other value , for example :
2n+1== O(2n) but  22n != O(2n) because  we can write 2n+1  as 2*2n and consider 2 as constant(c1) but in case of  22n  ,it can be written as 2n *2n and here 2n cannot be considered as a constant. So it can’t be considered as O(2n).
  • f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n))  because in that way only it will be upper bounded by g(n) as well as lower bounded by g(n) for any constants c1,c2.
  • We generally neglect lower order terms for analyzing the complexity of algorithm. eg( an2+bn+c)  could be written as O(n2))
Floors and ceilings:
floor(x) = \lfloor x\rfloor  is the largest integer not greater than x and ceiling(x) =  \lceil x \rceil is the smallest integer not less than x.
for example floor(9.6)=9 and ceiling(9.6)=10.




Sunday, 30 December 2012

Complexity Analysis

I am presenting simple comlexity analysis of algorithms for that I'll use Insertion sort algorithm:

Insertion sort algo:

Insertion Sort(Array A)
          
  for int j=2 to A.length{                          // it will loop through for n times, cost= c1*n
     key=A[j]                                             // it will loop for n-1 times, cost= c2*(n-1)
     i= j-1;                                                  // it will loop for n-1 times, cost= c3*(n-1)   
     while( i>0 && A[i]> key){      // depends on condition being true, cost= c4 *(∑ tj where j=2 to n)
       A[i+1]= A[i];                                   // cost= c5 *(∑ tj-1 where j=2 to n)
       i--;                                                   // cost= c6 *(∑ tj-1 where j=2 to n)
     }
     A[i+1]=key;                                     // cost= c7 *(n-1)
  }

where all c1,c2 etc are constants, so the total time to excute this algorothms would be:

T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(∑ tj where j=2 to n)+ c5 *(∑ tj-1 where j=2 to n)+ c6 *(∑ tj-1 where j=2 to n)+c7 *(n-1)

In the worst case the inner while loop will execute for each element and hence will sum up as:
(∑ tj-1 where j=2 to n) = 1+2+3+4+-------+n-1 =  n*(n-1)/2
that will be equal to n^2.

So  now T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(n^2)+ c5*(n^2)+ c6*(n^2)+c7 *(n-1)

and since n^2 is the maximum term , ignoring lower order terms will give us :
T(n)=O(n^2).

This approach is very useful in analysis of all the algorithms which uses loops and gives basic idea of how to derive complexity.
Post comments if you face any issue to analyze complexity or any problems in this method to follow.