Monthly Archives: January 2011

Perplexing Probability – Things are not always obvious

Note: Below mentioned story is a purely hypothetical one. Think of it as just another probability problem. Don’t get into the complexities of real world. Everything you need to ponder upon is already mentioned in the story.

After the recent India-SA test series, the big question is which is the better test team. Obviously, if we go by test rankings India is currently the number 1 test team and the mighty SA the second in the list. But ICC decided to organize a three match series between the two sides to decide the ultimate team. They propose to Indian cricket team – if they can win at least two consecutive matches they will be declared the number 1 team of all times. The three matches will be played alternatively in India and South Africa. The Indian team can decide the order, either they can choose to play in India-SA-India or SA-India-SA. The ICC also lifted up the 5 day constraint – which means each match will end up with a result for sure, no draw. For quite obvious reasons the probability of India winning a match in India is more than India winning a match in SA.

Now the question in front of BCCI is to select the order of venues to maximize the probability of India becoming the best test team of all times.

BCCI first came up with the order – India-SA-India, which also sounds obvious. But, when they later realized that India has to win at least two consecutive matches to prove their supremacy, they changed the order to SA-India-SA which is not so obvious but of course the correct strategy (at least probabilistically).

Do some calculations yourself to appreciate the BCCI’s final decision.

What’s wrong with binary search!

7 Replies

There’s a bug in the code of “Binary Search” as most of us write it. When asked most of us code binary search as -

int binary_search(int *a, int len, int key)
{
int low = 0;
int high = len-1;

while (low <= high)
{
int mid = (low+high)/2;
int val = a[mid];

if (val < key)
{
low = mid + 1;
} else if (val > key)
{
high = mid - 1;
} else
{
return mid;
}
}
return -1;
}

Now, try to find the bug in the above code. The bug surfaces if the array is too large. If the length of the array is too large, line number 8 in the above code would cause the variable “mid” to overflow and hence will have a negative number and the code breaks. A very simple solution would be to replace line 8 in the above code with -

mid = low + (high-low)/2;

So, you see how bugs could creep in your code. To see more detailed discussion on how the bug was discovered and a couple of more elegant, efficient solutions check out this Google Research blog – http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

What’s been keeping me busy these days?

2 Replies

Of late, I have not been adding new pages to my blog. A lot has changed since I last blogged. From an undergrad student at IIT Guwahati to a Software Developer at Adobe India now. Transitioning from one role to another took a lot of time. Now, when I think, I am probably comfortable in the new role, I have started exploring new stuffs. I will enumerate few of the interesting stuffs I have been looking into since last one month or so.

Page Replacement Algorithms – I have been digging into various page/memory replacement algorithms. For the uninitiated ones here is the wikipedia page which explains various of those algorithms in short – http://en.wikipedia.org/wiki/Page_replacement_algorithm . I explored the memcached cache replacement policy and its implementation. I will write more about my reading on this subject in my later posts. I will also try to attach implementations of few of the algorithms.
OpenStack – Openstack is an IaaS Cloud Computing open source project started by Rackspace and NASA. There are basically two sub projects of Openstack – Nova and Swift. I have read the overview of both the sub projects and I am trying to dig more into Nova. I would love to contribute to this awesome project and will start off soon by accomplishing some low hanging fruits of Nova. Will write more about my experience and technical insights I gain in my later posts.
Art of Trading – I have been looking into various articles related to algorithmic trading. I started off with Optimal Stopping Theorem. Depth first search of the wikipedia article led me to Search Theory, Odds Algorithm, the interesting “The Marriage Problem” . But things start getting mathematically complex once I start digging into Automated Trading Algorithms. ATQs use techniques from signal processing, game theory, gambling Kelly Criterion and time series analysis. Miles to go. Phew!

And yeah, I have also been listening to two songs continuously (read frequently) these days – Madno Re from Lamhaa (2010) and Naam Adaa Likhna from Yahaan (2005).