Randomized Algorithms

Since my mind is wandering around my work, I couldnt think of anything fruitful to report..:).. Interestingly, it has been my observation that any finding stems from simple facts that we experience and solve in a day to day life. Just that it has not been documented and thought through in an academical sense. Recently, I heard of applying randomized algorithms for certain technical problems.

The question is this. If you have a 1000 apples and one of them is bad, how will you detect it? The obvious solution would be to check all 1000 apples till you find the odd one out. If you get lucky, you will end up detecting the odd one out very quickly. On a bad day, you may end up looking at all the 999 apples before finding that the 1000th apple was the bad one. How does one solve this problem? Though people have come up with clever ways to solve the problem, when the state space explodes, it becomes a very difficult problem to solve.

Probability comes to the rescue. The question is twisted now. If you have the time to pick only 10 apples at any time before you have to move on, which 10 apples would you pick. What is the probability that you will succeed in getting the odd-apple out by picking only 10 apples. It has been studied probabilistically that, a smaller sample randomly picked from a given group can still detect the odd one out with very high probability. I dont want to get into the math of it. In everyday life, we apply the same principle in a lot of cases where we face complex decisions because trying to analyse all possibilities could be a night mare and we dont have that much time. In the big picture, when there are more uncertainities, we are probably better off by solving a smaller set of finite problems than trying to solve the bigger problem itself...

Oopsie...

Scenario 1:
Hmm..This looks interesting ...But, why do they have books here ? Isn't it meant for people though I am sure mom and dad can never sit here.Looks like a fundu hideout incase of timeout.Maybe, I should give it a try and see if I can make it..After all ,it is just slightly taller than me, not like my high chair . For a change, I can climb up on my own instead of someone lifting me. People never realise how painful it is everytime they lift me using my arms. There...(sighing) finally...Oh! I think I have to bend to fit myself in..Comeon , Nat , you can make it...What do I do now? Is that Dosa I am smelling...Mommy !! OH NO !! I cant move my head..MOMMY !!! MOMMY !!


Scenario 2:
Oh ! its 12 already ! Time for my house tour ...Hey, what the heck? How did I miss this all these days? This looks very similar to my toy house. What happened to my elmo? Oh God ! ( Running to the toys' room which has a similar stand with toys in it) There..Whew! For a minute, I was about to scream looking for my elmo.What a waste it would have been..( Back to the living room)..Hmmm...Lets see, maybe, just maybe, dad was kind enough to get me my own house where I can sit in and be comfortable. But, why has he kept it here? Shouldn't it be in my room?Anyway, I will give it a try . If I have enough room, I can bring elmo also to stay with me.I think elmo goes in foot first but with my height, I would have to try head first...Not bad..I am almost there. Just a small bend of my head and voila !! Isn't this great !! Oopsie..wait a minute...What is this? How do I turn now ?Oh no! MOMMY !! MOMMY ! WHAW.......HELP !!

Now, thats our Nathaniel....As naughty as it gets...:-)