Entropy .. Simply !

In information theory, entropy is the average amount of information contained in each message received. Let's dig into an example directly,
the four possible outcomes (events) that could occur if you flipped a coin twice (experiment) are:
Head then Head , Head then Tail , Tail then Tail , and Tail then Head .

Note that the four outcomes (sample space) are equally likely, so each probability should be equal to 1/4 :
P(X₁=Head & X₂=Head) = 1/4 ,
P(X₁=Head & X₂=Tail) = 1/4 ,
P(X₁=Tail & X₂=Tail) = 1/4 , and
P(X₁=Tail & X₂=Head) = 1/4 .

The entropy for the previous example is given by:

H(X)=−ΣiP(x)log2[P(x)]=

 = - (1/4) log₂(1/4) - (1/4) log₂(1/4) - (1/4) log₂(1/4) - (1/4) log₂(1/4) = 2.

This means that you need 2 bits to store the actual status at any moment that comes out when conducting that experiment (event).
---------------------------------------------------------------------------------------------
Let's have another simple example. If we expect if the sun will rise tomorrow or not (experiment), we obtain two possible outcomes (sample space):
P(SunRisesTommorrow) = 1 and
P(SunWontRiseTommorrow) =0 .
  

So, the entropy is : = - (1) log₂(1) - (0) log₂(0)  = 0.

This means that we don't need any bits to store the actual status of that experiment, because we are 100% sure that tomorrow the sun will rise (P(SunRisesTommorrow) = 1).
---------------------------------------------------------------------------------------------
"The entropy of the unknown result of the next toss of the coin is maximized if the coin is fair (that is, if heads and tails both have equal probability 1/2). This is the situation of maximum uncertainty as it is most difficult to predict the outcome of the next toss; the result of each toss of the coin delivers one full bit of information.
However, if we know the coin is not fair, but comes up heads or tails with probabilities p and q, where p ≠ q, then there is less uncertainty. Every time it is tossed, one side is more likely to come up than the other. The reduced uncertainty is quantified in a lower entropy: on average each toss of the coin delivers less than one full bit of information." Wikipedia

C Function with Variable Number of Arguments

One usually need to implement a function where the number of arguments (parameters) is not known, or is not constant, when the function is written. Just like the printf function. The following example shows that in terms of code:

int f(int, ... ) {

        .

        .

        .

}

int g() {

        f(1,2,3);

        f(1,2);

}

Let's consider a simple example, we need to implement a function GetSum that calculates the summation of any number of integers.

So, such function takes variable number of arguments.

The first one is Size: the number of integers to calculate the summation for.

Then it takes each integer of the numbers to be added as a separate parameter.

You can call it to calculate the summation of two numbers (4+30), like :

GetSum(2, 4, 30); /* returns 34 */

Or to calculate the summation of 5 numbers (7+10+1+15+3), like :

GetSum(5, 7, 10, 1, 15, 3); /* returns 36 */

The implementation of GetSum is as follows. The comments describe everything:

#include <stdarg.h>

int GetSum(int Size, ...)

{

    int Sum = 0.0;

    

    // 1- Create Variable List

    va_list variable_list;

    // 2- Initialize variable_list to retrieve data

    //      starting from the address of the parameter Size

    va_start(variable_list, Size);

    // 3- Access all the arguments assigned to variable_list

    for (int Index = 0; Index < Size; Index++) {

       Sum += va_arg(variable_list, int);

    }

    // 4- Clean memory reserved for variable_list

    va_end(variable_list);

    return Sum;

}

Hidden Markov Model HMM .. Simply ! (1/3)

In this series of tutorials, I will explain very important concepts about the probability theory in a simple way.We will simplify the concept and mathematics of Hidden Markov Models (HMM). It is named after the Russian mathematician Andrey Markov. Almost all present day large vocabulary continuous speech recognition (LVCSR) and text/handwriting recognition systems are based on HMMs! HMMs lie at the heart of almost all of the modern successful speech and text recognition solutions.

In this tutorial, we will explain what a Markov Models is and what are the probability theory concepts that are related to it. This topic is very essential to understand HMM. For this purpose, let's try to figure out this problem: we need to make a probability model that we can use to predict the weather in Cairo for tomorrow.

    

For the weather state, let's assume we only have three possibilities:

• State 1: Sunny
• State 2: Cloudy
• State 3: Rain or Snow (Rain/Snow)

By carefully examining the weather of Cairo for a long period of time, we found following weather change pattern:

--------------------------------------------------------------------------------------------

What you see in the previous image is a Markov Model diagram that can be used to predict the weather in Cairo. In that model:

if today is Sunny, the probability of having a Sunny day tomorrow = 0.6,

the probability of having a Cloudy day tomorrow = 0.3,

and the probability of having a Rain/Snow tomorrow = 0.1. It's logic that the summation of these values is equal to one, because they cover all the three possibilities of tomorrow's weather given that today is Sunny. The summation of outgoing edge weights from every state should be one.

Also, note that the weather of tomorrow depends on today and is totally independent on the weather of yesterday. In other words, the next state depends only on the current state and not the previous one(s). A stochastic process (a system whose state is non-deterministic: random) has the Markov property if the conditional probability distribution of future states of the process (conditional on both past and present values) depends only upon the present state, not on the sequence of events that preceded it. A process with this property like our process is called a Markov process.

Our weather problem looks simple, we can estimate the different weather probabilities for some days easily. But because that the purpose of these tutorials is to explain HMM which is more complex. We need to define properties, like the ones in the previous two paragraphs, in terms of mathematics. So that when things are getting complected, we have some nice equations that can resolve it. So now, let's make some definitions concerning Markov Model:

• Number of States :
  N, where N=3 in the previous weather example.

• 1st order Markov assumption :
  P( S_t = X | S_t-1 = Y | S_t-2 = Z | S_t-3 = W | ... | .... ) = P( S_t = X | S_t-1 = Y ) ,
  In words,
  the probability of having a state X at some day (t)
  giventhat in the previous day (t-1) it was state Y,
  and that the day before it (t-2), it was state Z,
  and that the day before before it (t-3), it was state W,
  and that the day before before before it (t-4), it was state ....
  and that the day before before before before it (t-5), it was state ....
  ....
  is equal to
  the probability of having a state X at some day (t)
  given
  that in the previous day (t-1) it was state Y.

• Stationary :
  P( S_t = X | S_t-1 = Y ) = P( S_t+1 = X | S_t+1-1 = Y ) ,
  In words, the probability of having a state X at some day (t) given that in the previous day it was state Y,is the same value regardless in which day am I.

• State Transition Matrix :
  , Where:
  a_xy = P( S_t = Y | S_t-1 = X ), 1 ≤ x,y ≤ N , with constraint a_xy ≥ 0,
  

• Initial state probability:
  πi = P( S₁ = X )
  In words, πi. is the provability of having the first day (the very initial first day, as if there are no days before it) to be state X.

• Conditional Property:
  P( S_t = X , S_v = Y ) = P( S_t = X | S_v = Y ) * P( S_v = Y )
  In words,
  the probability of having a state X at some day t
  and (means that both events should happen)
  having a state Y at some other day v,
  is equal to
  the probability of having a state X at some day t
  given that we (will) have a state Y at some other day v
  multiplied by
  the probability of having a state Y at the day v.

• Chain Rule:
  P( S₁ = X | S₂ = Y | S₃ = Z | ... | .... | S_T-1 = W | S_T = U ) =
  P( S₁ = X ) * P( S₂ = Y | S₁ = X )
      * P( S₃ = Z | S₁ = X,S₂ = Y ) * ... * P( S_T = U | S₁ = X,S₂ = Y,S₃ = Z, ... ,S_T-1 = W )
  And using the 1st order Markov assumption definition/property:
  = P( S₁ = X ) * P( S₂ = Y | S₁ = X ) * P( S₃ = Z | S₂ = Y ) * ... * P( S_T = U | S_T-1 = W )

--------------------------------------------------------------------------------------------

Now, let's go back to our previous Cairo weather example, we will have a state transition matrix as follows :

, and let's say we have an initial state properties as follows : πi = {0.9, 0.08 , 0.02}. Note that the summation of the previous group should be equal to one. We need to answer a question:
" What is the probability that the weather for the next five days will be: “sunny-rain-sunny-cloudy-cloudy” when today is sunny? ". We should remember that sunny is state 1, cloudy is state 2, and rain/snow is state 3. The solution to that question is as follows:

P(O | model) = P (S₁ = 1 , S₂ = 1, S₃ = 3, S₄ = 1, S₅ = 2, S₆ = 2 | model)
  =  P (S₁ = 1) * P (S₂ = 1 | S₁ = 1) * P (S₃ = 3 | S₂ = 1) *
                          P (S₄ = 1 | S₃ = 3) * P (S₅ = 2 | S₄ = 1) * P (S₆ = 2 | S₅ = 2)
 = π1 * S₁₁ * S₁₃* S₃₁ * S₁₂ * S₂₂ = 0.9 * 0.6 * 0.1 * 0.4 * 0.3 * 0.2 = 0.001296,
which means: 0.1296 % !

In the next article we will explain about Hidden Markov Models.
I will be glad to answer your questions or hear your feedback in the comments.

My Interview with Egyptian TV (14 December 2014)

14 December 2014 - Channel 2

NP Problems Tutorial with Coding Examples [By Solving a CodeJam Problem]

What is NP?

NP is the set of all decision problems (question with yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(n^k) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.
--------------------------------------------

What is P?

P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since it can solve in polynomial time, it can also be verified in polynomial time. Therefore P is a subset of NP.
--------------------------------------------

What is NP-Complete?

A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x. In other words:

1. x is in NP, and
2. Every problem in NP is reducible to x

So what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly then all NP problems can be solved quickly. Also see What’s “P=NP?”, and why is it such a famous question?
--------------------------------------------

What is NP-Hard?

NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having 'NP' as a prefix. That is the NP in NP-hard does not mean 'non-deterministic polynomial time'. Yes this is confusing but its usage is entrenched and unlikely to change.

Photo From Wikipedia [1]

--------------------------------------------

P Problem Coding Example:

In Google's CodeJam Africa 2010, Qualification Round, there were a problem called Store Credit. Here the Description of it:

• Problem: You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).

• Input: The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:
• One line containing the value C, the amount of credit you have at the store.
• One line containing the value I, the number of items in the store.
• One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.
• Each test case will have exactly one solution.

• Output: For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first. Limits: 5 ≤ C ≤ 1000, 1 ≤ P ≤ 1000Small dataset: N = 10, 3 ≤ I ≤ 100Large dataset: N = 50, 3 ≤ I ≤ 2000

• Sample: 

Input: 

3

100 

3 

5 75 25 

200 

7 

150 24 79 50 88 345 3

8

8

2 1 9 4 4 56 90 3

Output: 

Case #1: 2 3 

Case #2: 1 4 

Case #3: 4 5

• C++ Solution:

#include <iostream>     //For std::vector

#include <fstream>      //For std::cout and std::cin

#include <vector>       //For std::vector

using namespace std;

int main(int argc, char ** argv)

{

    std::ifstream infile(argv[1]);

    if(!infile) {

        std::cout << "could not open " << infile << std::endl;

        return 0;

    }

    std::ofstream outfile(argv[2]);

    if(!outfile) {

        std::cout << "could not open " << outfile << std::endl;

        return 0;

    }

   

    /*should be char if c, but with C++ this

    will let "infile >>" to read only one digit*/

    unsigned short numberOf_testCases;

    unsigned short credit, numberOf_Items, itemPrice;

    std::vector<unsigned short> allItems;

   

    infile >> numberOf_testCases;    //Number of Test Cases

    for(unsigned int i=0; i<numberOf_testCases; i++){

        infile >> credit;            //Credit

        infile >> numberOf_Items;    //Number of Items

        for(unsigned int j=0; j<numberOf_Items; j++){

            infile >> itemPrice;

            allItems.push_back(itemPrice);

        }

       

        bool breakBool = false;

        for(unsigned int j=0; j<allItems.size(); j++){

            for(unsigned int k=j+1; k<allItems.size(); k++){

               if ((allItems[j] + allItems[k]) == credit)

               {

                 outfile << "Case #" << i+1;

                 outfile << ": " << j+1 << " " << k+1 << endl;

                 breakBool = true;

                 break;

               }

            }

            if (breakBool)

                break;

        }

        allItems.clear();

    }

   

    return 0;   

}

--------------------------------------------

NP Problem Coding Example :

The previous example problem is not an NP problem. The previous solution implementation is of order O(n^2) at worst case.

Now, we will modify the previous problem slightly to make it an NP complete problem (A subset sum problem).

• Problem Modification: From the item list you have created for the store, you should buy items that you can add up to the entire value of the credit.
  You will buy any number of items not only two.

• Input Modification: No modifications.

• Output Modification: No Modifications.

• Sample: 

Input: 

2 

100 

3 

5 75 25

8 

5

4 2 1 1 5 

Output: 

Case #1: 2 3 

Case #2: 1 2 3 4

• C++ Solution: This solution is using a dynamic programming (a bottom-up approach).

#include <iostream>

#include <fstream>

#include <algorithm>    // std::reverse

#include <vector>       // std::vector

using namespace std;

std::vector<unsigned short> getIndecesOfSum(

    std::vector<unsigned short> numbers, int n, unsigned short sum);

int main(int argc, char ** argv)

{

    std::ifstream infile(argv[1]);

    if(!infile) {

        std::cout << "could not open " << infile << std::endl;

        return 0;

    }

    std::ofstream outfile(argv[2]);

    if(!outfile) {

        std::cout << "could not open " << outfile << std::endl;

        return 0;

    }

   

    /*should be char if c, but with C++ this  

    will let "infile >>" to read only one digit*/

    unsigned short numberOf_testCases; 

    unsigned short credit, numberOf_Items, itemPrice;

    std::vector<unsigned short> allItems, selectedItems;

   

    infile >> numberOf_testCases;    //Number of Test Cases

    for(unsigned int i=0; i<numberOf_testCases; i++){

        infile >> credit;            //Credit

        infile >> numberOf_Items;    //Number of Items

        for(unsigned int j=0; j<numberOf_Items; j++){

            infile >> itemPrice;

            allItems.push_back(itemPrice);

        }

       

        selectedItems = getIndecesOfSum(allItems, 

                                   allItems.size(), credit);

        outfile << "Case #" << i+1 << ": ";

        for(unsigned int j=0; j<selectedItems.size(); j++){

            outfile << selectedItems[j] << " ";

        }

        outfile << endl;

        allItems.clear();

        selectedItems.clear();

    }

   

    return 0;   

}

std::vector<unsigned short> getIndecesOfSum(

      std::vector<unsigned short> numbers, int n, unsigned short sum)

{

    std::vector<unsigned short> IndecesOfSum;

    bool DP_Matrix[sum+1][n+1]; //Dynamic Programming Matrix

    // If sum is 0, then answer is true

    for (int i = 0; i <= n; i++)

        DP_Matrix[0][i] = true;

    // If sum is not 0 and numbers is empty, then answer is false

    for (int i = 1; i <= sum; i++)

        DP_Matrix[i][0] = false;

    // Fill the DP_Matrix table in bottom up manner

    for (int i = 1; i <= sum; i++)

    {

        for (int j = 1; j <= n; j++) //Row then Row

        {

          /*If DP Matrix element is true,

          then next elements in the row is true.*/

          DP_Matrix[i][j] = DP_Matrix[i][j-1]; 

          if (i >= numbers[j-1])

           DP_Matrix[i][j] = DP_Matrix[i][j] || 

                              DP_Matrix[i - numbers[j-1]][j-1];

        }

    }

    //Print the Dynamic Programming Matrix

    /*for (int i = 0; i <= sum; i++)

    {

        for (int j = 0; j <= n; j++)

            printf ("%4d", DP_Matrix[i][j]);

        printf("\n");

    }*/

   

    for (int j = n; j >= 1; j--)

    {

        if(sum - numbers[j-1] >= 0 && 

                DP_Matrix[ sum - numbers[j-1] ][j-1])

        {

            IndecesOfSum.push_back(j);

            sum = sum - numbers[j-1];

        }

    }

   

    std::reverse(IndecesOfSum.begin(), IndecesOfSum.end());

   

    //return DP_Matrix[sum][n];

    return IndecesOfSum;

}

--------------------------------------------

A More Difficult Problem:

Now we are going to make this problem more difficult.

• Problem Modification: From the item list you have created for the store, you should list all the combinations of items that you can add up to the entire value of the credit. You will buy any number of items not only two.

• Input Modification: No modifications.

• Output Modification: The program should list all the possible combinations of items that you can bought with the received credit C. Now there is no unique solution for each test case.For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit for the first solution. If there are other solutions, it should be also written after it and be separated with a comma ",".

• Sample: 

Input: 

2 

100

3 

5 75 25

8 

5

4 2 4 1 1

Output: 

Case #1: 2 3 

Case #2: 1 2 4 5 ,  1 3 , 2 3 4 5

• C++ Solution: Think about it. I will post the answer in a coming post though ;-)

• A Question: Now the problem is more difficult, but does it still an NP Complete problem ? Wait for the answer in the coming post.

--------------------------------------------

To compile and use the above codes:

1. Add it to a file: D:\Test_Project\main.cpp,
2. then make a new patch file: D:\Test_Project\Compile.bat:, with the content:
   g++.exe -Wall -c -g main.cpp -o main.oppg++.exe -static -static-libgcc -static-libstdc++ -o "program.exe" main.opppause
3. Run (Double Click) that patch command to build your executable D:\Test_Project\program.exe.The "pause" command is to hold the CMD window for you to check if the C++ compilation was successful or not.Don't forget to install the a C++ compiler, for the patch file to work correctly.If you are using windows you can install the GNU Compiler by downloading and installing MinGW (Minimalist GNU for Windows).
4. Open CMD, then write the following command:D:\Test_Project\program A-large-practice.in A-large-practice.outDon't forget to put the file D:\Test_Project\A-large-practice.in with the input test cases, and to create a new empty file D:\Test_Project\A-large-practice.out.
5. Check the results into D:\Test_Project\A-large-practice.out.

--------------------------------------------

References:

1- http://en.wikipedia.org/wiki/NP-complete

2- http://stackoverflow.com/questions/210829