The Parity Bit

Here’s an interesting mind bender for you (do note that this question is used in a lot of job interviews) -

A warlord has captured 1000 villagers, and has decided to put their wits to test. He has put 4 different coloured hats (say Red, Blue, Black and White) on these thousand villagers and arranged them randomly in a long queue. The arrangement of this queue is such that each villager can see all the villager’s hats in front of him, but he cannot see the villagers behind him.

Each of them now have to guess what colour their hat is. If it is the right colour then the villager is allowed to live and is freed, if not … then let’s just say he won’t be having any more headaches.

The villagers are allowed to discuss as a group to decide on a protocol (an algorithm of sorts) to decide how to call the colours so that the maximum no. of villagers survive. What is this algorithm and how many villagers will survive?

Hint: The title of the post

Taken from Wikipedia,

A parity bit is a bit that is added to ensure that the number of bits with the value one in a set of bits is even or odd. Parity bits are used as the simplest form of error detecting code.

The villagers have to use the concept of parity in their answers. Instead of taking a guess at what colour his hat is, the last villager is the parity bit. His answer gives an indication to everyone else in the queue as to what could be their colours. How? Here is so -

Each colour is denoted a no. (Red=1, Blue=2, Black=3, White=4). Since the last man can see all the hats in front of him, he takes a total of all the number before him and does an operation (total mod 4). This is the parity (or the error-correction answer). Now the man in front of him can see all the hats (except his of course) and also knows this value error-correction value. What he has to do is do the same operation for all the hats in front of him, and subtract that value from the previous mod. That’s the colour of his hat.

The cool thing about this is that even if there is one fool of a villager who miscalculates, the villager next to him can detect this error and can correct it immediately.

Now, where would we be using this? (In other words, why did I bother with this problem?)

Networks! Computer networks use the concept of parity bit to detect transmission errors for quite some time now (have you ever faced that pesky CRC error? That’s your parity bit right there).

Read More

wordpressspanner.jpg

WordPress Theme!

wordpress-spanner Created or rather tweaked my first WordPress theme ever. Have taken the Magazine theme and with the help of Angad worked out a flashy new theme for our latest blog at work.

Interesting to note that many people do only this for a living and some of the themes fetching a whopping $200 per piece. Makes me want to learn WordPress as an engine and contribute (eh … loosely using the term here!) to the WP community.

See the series of blogs under this theme shortly here and here.

Read More

Gartner Hype Cycle 2009

I first came across the Hype Cycle in 2008, immediately, I posted about it here. Back then, the Web 2.0 and SOA was considered to be a market failure. Everyone who was anyone in the web development arena was claiming to create “Web 2-point-oh” applications, without knowing what that term meant. I know about an entrepreneur who pitched the idea of a Web 2.0-based e-commerce portal to a VC. In return, the VC asked one simple question – “Do you know what Web 2.0 means?”

Hype cycles are just that, they indicate the evolution of the system and its mainstream adoption with the amount of hype it is creating among the society. They also are an indication to future market leaders – companies which are poised to take off due to the right adoption of technology.

gartner_hype_cycle09bSo, what do you think you should invest into now? Do you think you will buy “the Kindle””? How about that power saving infrastructure? What to do with KM?

Kudos to Gartner for coming up with this framework.

Read More

Web 4.0: The Enabling Web

Forgive me, this post is going to be a long one.

In the brief span of its existence, the web has evolved at such an alarming rate, that it outstrips evolution of any living organism. Even as Indian web users and web development companies are creating (and using) Web 2.0 platforms, the more developed nations are already talking about Web 3.0, the semantic web.

Picture2

Not so surprisingly, I have found to my chagrin that 80% or more of the Indian populace associate Web 2.0 with client side technologies instead of a collaborative technology. People associate it with all the wrong ideas … I do not blame them. Awareness has always been the bane of comprehension. Having said that, I decided that it would do some good if we can somehow capture the evolution of the internet in these already popular phrases, and somehow manage to extrapolate what the next stage could be – so that we are prepared when it comes ;-)

Or even better, a host of Indian companies could bring in the era of Web 4.0: The Enabling Web. So what are these evolutionary milestones?

Web 1.0: The Information Superhighway

This is the internet of yore. Those were the days when people would make separate HTML pages and upload it on the net. Content was written within these pages and uploaded. It was authoritative in nature, since most of these sites were a one way communication stream. People came to different sites with the sole aim of gathering information – hence the name, the Information Superhighway.

Web 2.0: A Collaborative Medium

This is the internet that we see around us these days. The web is more social now, its a place to meet interesting people – to collaboratively create content. Content is not written within pages, content is created by the users themselves. The more the users, the more the content. What the developers create is a platform which enables this co-creation between the users. A great example of this is Wikipedia or IMDB.

Web 3.0: A sense making layer

The new era of internet is coming, this can somehow make sense out of the user’s inputs and act accordingly. So when I say “Show me a blue lotus”, the internet should show me the image of a blue car instead of a blue flower. How does it do this? It already has my preferences for cars over flowers somewhere. This is where collaborative filtering mechanisms and business intelligence algorithms are used to correctly profile the user. The internet is capable of understanding what the user is speaking. It differentiates a Gandhi from a Hitler. Some examples of this would be WolframAlpha or Amazon.

Web 4.0: The Enabling Web

So what happens when the web begins the “understand” the user. The sole question is – “What’s the point?”. If it can understand the user, it can also understand the purpose with which the user is driven to visit a particular web application. And, if that can be done, then it won’t be too difficult to understand and provide what other resources would help the user reach his outcome. The web suddenly becomes a more intertwined place with each web application talking to others, so as to provide the best experience to its user. Not only experience, but to ensure that the user is enabled with the right set of resources to get his job done. The purpose of the user is kept at the center. That’s my vision for web 4.0 akin to a more evolved Ubiquity extension of Firefox.

Read More

Changing Communities through Vector Algebra

This is a follow-up post of my previous post on Perspectives and Co-ordinate geometry. Each individual’s perspectives form the different axes on which the individual perceives the world – and judges the world, so you have (happiness-sorrow axis, good-bad axis, moral-immoral axis, ethical-unethical axis, and so on). Each of these axes define who you are, your values, your beliefs, et al. If I were to map each of these axes against the society’s axes, then we can plot an individual on the society space (its an n-dimensional space, mind you).

Now, get this. The origin of the society (the norms dictated by the society) represented by (0,0,..,0) would be at a certain distance from your own origin say (1,2,1,-4,…,3). The vector (going outwards from the origin) which connects your origin to the society’s origin is your vector of existence. Every individual has his vector of existence. The people who are afraid of society and peer pressure have their origins closest to the society’s origins. Carefree people tend to be away from that origin. The more deviant you are to the society, the further you would be from the origin.

What makes a society? You, me and everybody. Thus, the society is a summation of these vector misalignments. And that my friend defines the origin of the society. Over a period of time, the origin naturally shifts – it shifts because many people change their origins (values, beliefs, etc), thus ensuring that the society also goes through that same shift (although much more gradually). A fact that would have been a taboo for the society would be a norm today. Take mini-skirts for instance or gay rights. Society changes its norms, because the collective changes their norms. The origin has shifted!!

Read More

Shaadi 2.0

No, its not about collaborative marriage over the web :-). Amol gave me this crazy idea. We were discussing the Indian SMS site, Vakow which enables us to push normal SMS into a web-based RSS/Atom feed. There are about a gazillion applications for an RSS feed. Well, this is just one such mashup between a practical application of Vakow and Google Reader.

Well to be honest, the title of the blog should not be Shaadi 2.0, but rather Event 2.0, but since we are using the my marriage as the event to cover, I decided to name the title so, well ..  and this one is more exciting na? So here is what we did.

  1. Register on Vakow, get a username and have your phone number associated with that username, so that you can SMS messages to your Vakow id.
  2. You are on track now, and you should be able to post a feed … now that your feed is set, we just need to integrate that feed with my marriage feed
  3. Send me the RSS link, I will add it in my Google Reader public folder, and voila!! You can view the sample page here.

People who cannot attend the wedding in person can keep on hitting the RSS page for an up-to-date status.

Read More