Sunday, February 19, 2012

World War IV ( Min Coin Change Problem ) Dynamic Programming Basic

"I know not with what weapons World War III will be fought, but World War IV will be fought with sticks and stones.
                                                                                                                                                                                   - Einstein 

World suffered a great loss due to World War III. World is taken aback to the age when there were no mobiles, no computers, no TV's , no machines. Every nation, religion, community, who survived the war, are in the process of building a new World.

Two countries "Megaricka" and "Hugeisia" are emerging as new super-powers. There is a huge conflict between these two nations. If the conflict is not resolved, soon the world will suffer from another world war, World War IV. To stop the World War IV, a messenger named Bellman from Hugeisia is sent to Megaricka to sign a peace treaty. Everything went well, but there were few people from Megaricka who were against this treaty. So on the return journey of Bellman, he was held back by these protagonist of Megaricka.

Now if Bellman does not reach Hugeisia within 20 days, Hugeisia will attack Megaricka which will lead to World War IV. Bellman, being held hostage, could'nt do anything but plan his escape route. After 6 days of planning, Bellman finally planned his escape route. He must return to Hugeisia before the eve of 13th day from next morning. Bellman needs to carry some food with him to survive the next 13 days. Only options left in front of him were 5 fruits. He knew how long he could survive by eating fruit of each type.

Type of Fruit   |   Mango   |   Pineapple   |   Orange   |   Papaya   |   Apple
------------------------------------------------------------------------------------------------------------------
 No of days            1                   2                      3                  4                5 
he can survive  
------------------------------------------------------------------------------------------------------------------
Weight                   1                   2                      3                  4                5 

Bellman's task was to find the combination of fruits he can carry with him which would weigh less and also at the same time, give him just enough energy to survive for 13 days. He could have tried all the combinations and found out the one which would suffice his need. But that would have taken long.

He remembered a technique called Dynamic Programming by which he can pick up minimum number of fruits that would let him survive for 13 days.

"Dynamic Programming : Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems. To solve a given problem, we need to solve different parts of the problem (sub-problems), then combine the solutions of the subproblems to reach an overall solution. " 

Now lets see how Bellman solved this problem. He split the problem of surviving for 13 days .

To survive 0th day he needs 0 fruits weighing 0 KG.


To survive 1st day he can select any from the 5 fruits.But if he selects anything but Mango, the weight will also increase, so he selects Mango.


To survive for 2 days he has 2 choices, 2 Mangoes or 1 Pineapple. In this case he selects 1 Pineapple. If he would have selected 2 Mangoes he would have had to carry two objects with him. So he makes a choice of 1 pineapple.


Similarly, he makes choices for all days till 13th day.

Days Options Bellman's Choice Total No of Fruits
0 No fruits 0 0
1 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 1 1 M 1
2 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 2 1 Pi 1
3 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 3 1 O 1
4 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 4 1 Pa 1
5 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 5 1 A 1
6 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 6 1 A,1 M 2
7 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 7 1 A,1 Pi 2
8 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 8 1 A,1 O 2
9 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 9 1 A,1 Pa 2
10 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 10 2 A 2
11 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 11 2 A,1 M 3
12 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 12 2 A,1 Pi 3
13 Min_Weight (M,Pi,O,Pa,A) & Days_to_survive = 13 2 A,1 O 3

* M = Mango , Pi = Pineapple , O = Orange , Pa = Papaya , A = Apple


Code :


public int getMinimumFruits(int [] no_of_days,int need_to_survive) { 
     
    int [] optimum_choices = new int[need_to_survive+1]; 
    optimum_choices[0] = 0; 

    for(int i = 1; i < optimum_choices.length;i++) 
        optimum_choices[i] = Integer.MAX_VALUE;

    for(int i = 1; i <= need_to_survive;i++) { 
        for(int j = 0; j < no_of_days.length;j++) { 
            if(no_of_days[j] <= i && optimum_choices[i- no_of_days[j]] + 1 < optimum_choices[i] ) {      
                optimum_choices[i] = optimum_choices[i- no_of_days[j]] + 1; 
            } 
        } 
    } 
    return optimum_choices[need_to_survive]; 
}


From the above table, we can see that Bellman will carry 2 Apple and 1 Orange which will weigh 13 kg and he can survive for 13 days on those fruits.

He could have selected 13 mangoes which would weigh 13 kgs and survive for 13 days. But with this selection he would have had to carry a total of 13 objects with him, which are far too many compared to the optimum selection of only 3.

Before the World War III similar problem named "Min Coin Change" problem was solved using this technique.

Our hope is on Bellman to save the World from World War IV.Lets hope and pray that he escapes from Megaricka and reaches Hugeisia on time. :)

Happy Reading :)

Wednesday, August 10, 2011

Prove Wrong Things Correctly


Good Evening,


I came across this proof which proves (1=2).I found this one very interesting and so thought of sharing with you.
Let me warn you that though this proof seems to be correct,it is wrong.
This is perfect example of proving wrong things correctly.


Step                                                                    Reason
1 . a = b                                              Given
2 . a^2 = ab                                       Multiplying both sides by a
3 . a^2 - b^2 = ab - b^2                  Subtract b^2 from both sides of (2)
4. (a-b)(a+b) = b(a - b)                  Factor both sides of (3)
5. a+b = b                                          Dividing both sides of (4) by (a - b)
6. 2b = b                                            Replace a by b in (5) As per (1) a = b,Simplify
7. 2 = 1                                               Dividing both sides of (6) by b

This is how we can prove 2 = 1,which is wrong.

**This proof was mentioned in "Discrete Mathematics and Its Application by Kenneth H Rosen" under "Mistakes in Proof" section
Try to find the mistake and write it in comments.

Sunday, July 31, 2011

Euclidean Algorithm at Pizza Place



Few days back, I went to a Pizza Place along with my girl-friend.Something was strange about this place.When the waiter was taking the order he asked us our respective age.We thought there must be some special offer for different age group so we gave him our ages.After sometime he got us a very tasty pizza.Wow! this place serves best pizza in the world.This place should be in Italy.

Normally pizza is cut into 2 or 4 pieces for 2 people.But this pizza was cut into 15 pieces,How can I equally share this pizza with my girl-friend.So I had to eat 8 pieces and left remaining 7 for my girl-friend.

Unlike my thought,no special discount was given to us,I had to pay whole bill (including taxes :( ).Thing which was bothering me was why the waiter asked us for our age and why pizza was cut in unusual manner.I asked manager of the place to clear my doubts,but he said its a secret and cant share it with anyone.

Restless and eager to know the relation between ages and no of pieces,So i visited the place again to find the relation.

Now this time we gave him our false ages and no of pieces in which pizza was cut was also different this time.I kept on revisiting the place to get the pattern and also pizza was really tasty.

I compiled following information while visiting the place

Information :

My Age  | My GF Age     | No of Pieces
------------|--------------------|-----------------
  24         |  21                   |  15
  44         |  28                   |  18
  23         |  17                   |  40 

From above data,
Lets consider 1st case :
Ages can be divided by 3 


Ans == >  My age = 8
               + GF age = 7 
                                 15 = No of pieces (Last Column)


2nd case : 
Lets divide Ages by 2



Ans == >  My age = 22
               + GF age = 14
                                 36 = No of pieces / 2 


Ages can be further divided by 2,which gives us,



Ans == >  My age = 11
               + GF age = 7
                                 18 = No of pieces (Last Column) 



3rd case : 



Ans == >  My age = 23
               + GF age = 17
                                 40 = No of pieces (Last Column) 


As both numbers are prime there is no common factor.

So it seems that we found the secret of Pizza Place.They divide the number until both numbers have a common factor and then they just add the numbers and cut pizza into that many pieces.

So its a problem of finding Greatest Common Divisor (GCD).
So how to find GCD of two given numbers.

Here is the algorithm
1. Start
2. Min = Minimum (a,b)
3. Loop till min >= 1
4. if(a % min == 0 && b % min == 0 )
     return min;
5. return 1; 


Code :


    public int gcd(int a,int b) {
        for(int i = Math.min(a, b); i >= 1; i--) {
           if( a % i == 0 && b % i == 0) {
               return i;
           }
}
return 1;
    }

The above solution just loops backwards from Min till 1 and checks whether both numbers can  be divide equally with the loop counter.
If yes, then we have our GCD Else it returns 1;

But what if  numbers are very large e.g  prime near to 10^6 and prime near 10^5 and less than 10 ^ 6.
In this case as both numbers will be prime numbers their GCD will be 1.

Above solution will take more time to return GCD for such large numbers.

So lets take another approach which is called Euclidean_algorithm to find GCD.
this algorithm is nothing but a recursive technique to find GCD of given two numbers.

Recursive function :  


gcd(a,b)    =    a                                                ...if b = 0 
                 =   gcd(b,remainder(a,b))              ...if a > b, b > 0


Code : 


    public int gcd(int a,int b) {
        if(b == 0) return a;
return gcd(b,a%b);
    }

Above recurrence reduces the problem in each step,thus we get GCD in fewer steps.

**GCD's are also helpful in finding Minimum Fraction (or Smallest Ratio).

So we have revealed the secret of Pizza Place and also learnt how to find GCD through programming.
Bye for now, Happy reading. :)


Friday, April 8, 2011

I don't want to work on Saturday (Josephus Problem)


Its Friday evening and I just got a news from our Project manager that all team members will be working on Saturday and only one will be spared.

My PM being nice guy doesn't show favoritism towards anyone.So he decided to play a game.

Game is simple.All developers will be standing in a circle.Counting will start from fixed position,every next guy will be eliminated from circle.The one who remains last will get holiday on Saturday.

This game will be played three times with fixed position changing all the time.so no luck factor here.

Ohh wait .. i know this game...Its a Josephus problem..I know where to stand in circle so i'll be the last guy to be eliminated.

Thank you MATHS..you are great.You saved me from coming on Saturday.

Well I was lucky all three times.Enjoyed my weekend.

Its Monday morning ..I am back to office..my colleagues asking me how come I was lucky all the time.Now they know..I calculated my position such that I was never eliminated from circle.They want to know this technique and I am sharing it here.

Well the game wasn't actually a game.It is one of the famous Problem in Maths called Josephus problem.

Josephus Problem Statement : In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.
There are people standing in a circle waiting to be executed. After the first person gets executed, certain number of people are skipped and next person is executed again. Then again, people are skipped and a person is executed. The elimination proceeds around the circle (which becomes smaller and smaller as people get executed), until the last person survives, and he is given freedom.


The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

The implementation of problem is simple.By creating circular link-list and manipulating those links survivor could be found out.But it does take time.And as we all know.Time is Precious.So lets solve the problem in Mathematical way.

This is recursive problem where after each round new circle is formed and again elimination process starts
The recurrence relation for problem is

f(n)  = 1               -- when n is 1
f(2n) = 2f(n) - 1     -- when n is even
f(2n) = 2f(n) + 1    -- when n is odd

If we calculate the values of n and f(n) we get a pattern:

n      1     2     3     4     5     6     7     8     9     10    11    12    13    14    15      16
f(n)   1     1     3     1     3     5     7     1     3     5      7      9     11    13    15      1


So when n is power of 2, f(n) is 1 and f(n) is increased by 2 until n is again power of 2.
This is an increasing odd sequence.

If we represent  n as :
n = 2^m + l

where m is largest power of 2 and l is left over value
And if we solve above recurrence relation substituting new value of n
we get

f(n) = 2l + 1.   (By mathematical induction) ** not showing proof here

This equation satisfies all values in table

Lets take example of 100

f(100) = 73

n = 100 = 2^6 + 36
m = 6 and l = 36
so survivor would be 73 (2*36 + 1)


This was the mathematical way to find out who will survive.

But there is also some other way.If we concentrate more, power of 2 comes into picture which reminds us of binary representation.

After representing values from table in binary format and comparing each solution for values of n, we will see that solution is one bit cyclic left operation.

e.g 
n = 100
100 = 1100100

After one left cyclic shift 
1001001 = 73


This is amazing.Well As I said its Monday Morning and don't want to work on Saturday,Getting back to work now..

Happy Reading,
Bye.

**Java Code for all techniques programmatic,mathematical will be sent on request.
Request can be made at satyajit.bhadange@gmail.com

Wednesday, March 30, 2011

Sieve of Eranthoses - Prime Number Algorithm


In the land of Egypt, Numbers were born.Natural Numbers,Whole Numbers,Positive Numbers,Negative Numbers,Rational Numbers,Irrational Numbers.And something strange happened then.No one believed what happened at that time.All Numbers decide to distribute themselves proportionately but few Numbers resisted.As they didn't distribute their value, their own value was retain by themselves and were considered Primes.
Soon they realize there could be more who can join their group.One, who cant distribute his value was given a task to find prime numbers from whole number group.
Time was flying and whole number group was unrest.Those who found there identity as Prime numbers were troubled by whole numbers.One was given a big responsibility and so he came up with easy logic.

He called each number from whole number group.
Divided that number with all numbers between 1 and number to be check.
If number was divisible by any of previous number it was put into whole number group.
Those who failed to divide themselves were given identity of Prime.

public boolean isPrime(int n) {
for(int i = 2; i < n;++i) {
if(n % i == 0) return true;
}
return false;
}

Prime Numbers were happy as they were getting their own identity.Few days later, first few prime numbers decided to celebrate and they went to One to invite him.To their surprise they found that one was still busy separating other Prime Numbers from Whole Numbers.Primes decided to help One.They called Eratosthenes,ancient Greek mathematician for help.

Eratosthenes asked whole numbers to line up. Few came up and were standing in line.
Counting started from Two as Two was first Prime Number
Two was asked by Eratosthenes to eliminate all numbers standing in line which are multiples of Two.
Next number left after first elimination was Prime again.
This continue for while,Numbers didn't know when to stop.
They asked Eratosthenes, when should they stop elimination.
He suggested :
Number, You multiply you by yourself.
If the Number you are getting after multiplication is less than Number standing last in the queue, you continue elimination.
And if it is greater,stop the elimination.

Algorithm : 
1 . Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
2 . Initially, let p equal 2, the first prime number.
3 . Starting from p, count up by p and cross out thus found numbers in the list (that will be 2p, 3p, 4p, etc.).
4 . Find the first number not yet crossed out after p (this number is the next prime); replace p with this number.
5 . Repeat steps 3 and 4 until p is greater than n.
6 . All the numbers in the list which are not crossed out are prime.

But difficulty here was all numbers cant stand in a single row at a same time.so Big whole numbers still don't know whether they are Prime or not

History became legend,legend became myth, Time of prime Numbers has now come.They are now basic building blocks of natural numbers,used in many encryption techniques etc.After knowing the importance of Prime Numbers, Whole Number offered Prime number to remain in their group.Prime numbers now belong to both the groups.And all numbers lived happily ever after.

** Java Code size is large so code will be sent on request.All request can be made at satyajit.bhadange@gmail.com or leave the comment with your email id to get Java code for Sieve of Eratosthenes algorithm.

Friday, March 25, 2011

Memoization - Please dont ask to me to compute same values



Recently I was having conversation with my Delly,and Delly was really mad at me because she thinks I ask her to do the same things again and again.Here is the conversation between us

Delly       : Hey user101...!!!
user101   : Hi Delly, wassup ..??
Delly       : I am sorry user101, but if you are going to use me like this then i am afraid i am gonna have to stop running your codes.
user101   : What happen..wats wrong..???
Delly       : Whenever you write recursive code ,you ask me to do same computations again and again, Its boring and I really hate it.And you also ask JVM (Java Virtual Machine) to increase stack size and heap space.
Delly       : They make fun of you.JVM thinks you are bad programmer when it comes to recursive technique.They want you to use iterative approach so that they dont have to extend their memory.
Delly       : So i dont want you to use me. :(
user101   : Ohhh..!! i see.
user101   : Sorry delly but this is what i have learned during my academics.And all my friends use the same recursive technique.i dont know how i can make it efficient and avoid your rework.
Delly       : There is a technique called Memoization,you can use that....
user101   : ohk...let me check it on wiki..
(after 5 min.....)
user101   : Wow...!!! this is cool.Thanks Delly I will write about this technique on my blog...bye for now
Delly       : You are my programmer....love you...bye...

Well guys as i promised to Delly I am sharing my knowledge on Memoization with you...

Give me product of 3 * 4  ??
its 12 we all know

Now please give me product of 3 * 4 * 5
60..? right

How did you compute that...?
You must have used result of 3 * 4 which is 12 and then multiplied it with 5,which gives us the answer 60

You guys are smart..my Delly isnt..?? (sssshhhhh)
she recomputes 3 * 4 again and then result of (3 * 4) * 5
Now i see why she is so mad at me.

Whenever we write recursive programs e.g factorial,fibonnacci we ask computer to do computations which are already done before.
Here is code of simple recursive factorial program :

public class SimplyRecursive {

public static void main(String... args) {
System.out.println(new SimplyRecursive().fact(5));
System.out.println(new SimplyRecursive().fact(3));
}

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

Now what above program does

fact(5)  = 5 * 4 * 3 * 2 * 1 * 0 = 120
fact(3)  = 3 * 2 * 1 * 1 * 0 = 6

Did you notice that for fact(3) we would have the answer if we would have saved our previous computations.

This technique of saving previously computed values is called MEMOIZATION.

I tried to implement this technique.It looked easy while reading but i had to put some serious efforts to make my code run using Memoization.The toughest part was how to save values,because in recursive approach all values are on stack and computed in descending order. So i don't have itermediate result in my hand to save.After scratching head for few hours i realized i should store values of compuation in recursion only.

Here is my modified code.

import java.util.HashMap;


public class Factorial_Memo {

private static HashMap<Integer,Integer>  map = new HashMap<Integer, Integer>();

public static void main(String[] args) throws Exception {
System.out.println(fact(4));
System.out.println(fact(8));
System.out.println(fact(6));
}

private static int fact(int n) {
if(n == 0) return 1;
if(map.containsKey(n)) return map.get(n);
int y = n * fact(n - 1);
map.put(n, y);
return y;
}
}

The key here is storing values in HashMap

int y = n * fact(n - 1);
map.put(n, y);

The above two statements will be executed only if value if not present in HashMap.This is how Memoization works.

If your are not java programmer,you don't get HashMap by default.Instead of writing code for creating HashMap you can use boolean and int array to store computed values.Make index of boolean array true while storing values.While reading,check if index value is true use index value of int array else compute value ,make index of boolean true and store value in an int array.

**Secret :
My Delly still dislikes many of my codes...she doesnt say anything but I can understand her.But she was really very happy when I did my Factorial_Memo.

Bye
Its time to get back to my Delly.

Wednesday, March 23, 2011

My First Blog


Hello Readers.

This is my first blog ,little confused with how to start and what to write so starting with my introduction.Myself Satyajit Bhadange,completed my B.E in Computer Science from Pune Universtiy. Currently I am working with service based software company.

My main interest is programming.These days programming is my biggest passion and soon i will start posting problems and solutions on this blog.Any new idea for solving problems posted would be welcome.