The Third Eye

A Christmas Carol Problem

During November/December months, my church conducts christmas carol rounds. Members assemble at a common location and then proceed to visit nearby houses in the area. At the end of the rounds, they then reassemble for lunch/dinner. Since I am lazy by nature, I have always wondered whether we take the shortest route while visiting all the houses. So for the mathematically inclined, let me go ahead and formally define the Christmas Carol problem.

Given a start point, stop point and N intermediate points, what is the shortest route that starts from the start point, visits all the N intermediate points exactly once and then end at the stop point? This is nothing but the classic Travelling Salesman Problem which unfortunately is NP hard i.e. there exists no algorithm than can meaningfully find the optimal solution for large values of N. The number of possible alternatives is O(N!). Since my church visits at most 12 houses in one stretch, this number turns out to be 12! or 479,001,600. Of course, our Carol captain does not perform this exhaustive search. Instead he often uses a heuristic called the Nearest Neighbor algorithm to find the route to follow. He starts from the start point and then proceeds to the nearest unvisited home. After visiting the house,  he then moves to the house that is unvisited and closest to his current location. 

But how good is this heuristic?  The graph below shows that the heuristic provides a reasonable approximation. Even when there are 11 houses to visit, the route found by the nearest neighbor algorithm is only 50% worse than the best possible route. However this gap widens as we need to visit more and more houses.

Is there a way out? Can we find a better solution with little effort? Apparently you can - here is one way to do it. Start with the nearest neighbor solution and then randomly swap two houses to generate a new solution. So for e.g. let us say we need to visit 6 houses (A, B, C, D, E and F) and the initial solution obtained from the nearest neighbor algorithm is A, C, B, D, E, F. We will then create a new solution by randomly swapping say B and E. The new solution will then be A, C, E, D, B, F. If the new solution is better than the current best solution, we will accept it. We then proceed to mutate the new solution in the same way to get the next solution. Here is what you get when you run the above algorithm for 1,000,000 iterations. 

For visiting 12 houses, this algorithm is about 500 times faster than brute force enumeration. It took 15 seconds to run in my i5 quadcore machine. You can see the law of diminishing utility at play here - improvements are plenty in the beginning and then they taper out towards the end. So it takes less than a second to reach close to 4% of the best solution but another 14 seconds to reach the best solution. 

To conclude, the nearest neighbor heuristic provides a good enough approximation to the Christmas Carol problem. But you can do even better, if you are willing to spend some processor cycles.

We are not our Government

Lately the India story has lost its sheen. 20 years ago, the Indian economy was freed from the shackles of government. But little has happened ever since. We still remain laggards in primary education and per-capita income. India is the youngest nation in the world. In order to reap that demographic dividend, we only have a window of opportunity of 10 - 15 years. To educate, train and employ 60 crore people is no mean task. It would require investments of a titanic scale. The governement would have to dig deep into its stashed away wealth to make that happen.

That raises an interesting question. When was the last time the Indian government ran a budget surplus? - how about never? I know of several Indians including myself who gleefully point out that the USA's only export today is U.S. dollars. The US can afford to be delusional since its currency remains the global tender for all transactions. But why won't an undeveloped country like India balance its books?

Meanwhile the government is busy redistributing wealth in the name of NREGA, Food Security and Right to Education. Instead of concentrating on its core competencies of delivering justice and law and order, we have a bureaucracy that continues to grow on the taxpayer's teats. Instead of becoming a force multiplier, the government today has become the albatross around India's neck.

We however are not our government. While our government has never generated a surplus, we Indians save 30% of our income. While our government runs dilapidated schools staffed by "ghost" teachers, we direct all our savings to educating our children. As soon as our children become adults, we urge them to escape the morass that is India. While I may grumble about the distinct lack of patriotism of my fellow citizens, I can at the same time sympathize with their frustrations. Love and respect is earned, not obtained by fiat.

I recently came across Openstreet Map India, where volunteers painstakingly piece together an open source map of India. The government run Survey of India was apparently created at txpayers' expense for the same purpose. But they remain missing in action. Openstreet Map is not an exception. All across India, groups of like minded people have banded together to make a difference. They all chant the same mantra - We are not our government. As long as they exist, there still is hope.

Kahen kya jo puchhe koi ham se Mir,
Jahaan mein tum aaye the kya kar chale.

- Mir Taqi Mir

Toastmasters Speech #9 - Every Child in School and Learning Well

Toastmasters Speech #9 has the objective of "Persuade with Power". You can do this by either inspiring people, convincing them or by issuing a call for action. In this speech, I have attempted to do the first two by talking about the dismal state of public education in India and the role of Pratham in ameliorating the situation.

 

When I was in the sixth grade, my family moved to a village. Since there were no good schools around, I had to take 3 buses and then walk a km to reach school. Imagine that! - a 6th grader taking 6 buses and 4 hours a day to go to school [Pause] and I consider myself one of the lucky ones.

For you see, there are 200 million kids in India who don't even get to go to school - that is 2/3rd the population of America. Of those that go to school, 100 million cannot read and 125 million cannot add or subtract.If you are poor in India, the doors of quality education are shut for you. And there is no shortage of poor people - a third of the world's poor are Indians. Education is their only salvation - their ticket to a better job, more money and mobility to escape the poverty at home. And yet, they are denied the very thing that will save them!

We can't complain that the government is not doing anything - The government of India spends 250 billions Rs a year to provide public education to its citizens. Yet India also suffers from the highest teacher absenteeism in the world. A quarter of its teachers are "ghosts" - no one has seen them or heard them in a classroom. And the results are telling - In 2009, India was invited to participate in the prestigious PISA testing program (PISA stands for the Program for International Student Assessment). The results were released this week - first the good news, we are better than Kyrgyzstan in math and reading. In science, we come dead last among all the 74 nations tested. A glorious moment indeed - I can already feel my chest puffing out in pride!

The public education system is a mess because teachers are not held accountable. They are protected by powerful unions. But there is no one to raise a hue and cry when a child drops out. This is where Pratham comes into the picture. Pratham is India's largest non-profit that works in the field of primary education. Pratham means First, Primary, Priority. Pratham feels that the government's first priority should be to ensure that every child is in school and learning well. It is not enough just to build schools and hire teachers. Instead you should judge an education system based on how well its students are learning. It accomplishes this in two ways - by looking at the supply and demand of education. On the supply side, Pratham works with volunteers to ensure that underprivileged children have access to good teachers and high quality books. On the demand side, it generates awareness among citizens about the state of their schools. It is often said that "Sunlight is the best disinfectant". Every year, Pratham carries out the Annual State of Education Report (ASER) which measures the efficacy of the public schools all over India. This improves accountability as citizens are able to decide for themselves how their neighborhood schools compare with others. From its humble beginnings in 1994, Pratham today has 65,000 volunteers and has touched the lives of 3 million children.

All that is well and good.. But why should you care? - because today India is standing at the crossroads. It is the youngest country in the world. If its teeming millions are not educated and are unable to find a job, trouble will soon follow. Civil unrest, religious discord and terrorism as more and more people fight for a shrinking pie. All of you must have seen the chaos going on in the Arab world. India has four times the population. Imagine what will happen when India erupts.

How to build a better company? - Part I

During Steve's party, Mike, Amrit and I were lamenting the state of corporate America. The discussions centered around the distinction between those who do (workers) and those who tell what to do (managers). There is a lot of resentment among the workers against MBAs who lord over them solely on the basis of their newly minted degrees. But is MBA alone the problem? I work in a technology company where all the managers have an engineering degree. Although we do not suffer from the MBA blight, there is still room for improvement when it comes to managing people.

As Amrit pointed out, one key problem is the disconnect between the managers and the workers. The company is often organized as a hierarchy with a single manager handling anywhere from 5 - 20 workers. The manager is often only dimly aware of a subordinate - what he does at work, what are his dreams/desires or how he gels with others. Instead of nurturing a team, he is instructed to maximize its output. He is told to ignore the fact that Mike is an actual living being and instead treat him as a fungible resource. Guess what happens when the objective is to squeeze the last drop out of the team? You end up creating an environment where sociopaths are encouraged to infest the managerial cadre. The problem has become so acute that books such as the "The No Asshole Rule" have become overnight bestsellers.

The other problem infecting managers is cluelessness. When managers are picked from within the company, the honor goes to the one who is the most productive. Unfortunately, your success in writing code/making widgets does not guarantee your success in managing people. People, you soon realize are altogether a different ballgame. Very few companies provide training or guidance to newbie managers to walk them through one-on-one meetings, team lunches or sharing information. At the same time, most newbies assume that work will be more of the same. They never take the initiative to learn more about management, identifying role models and approaching them for mentoring.

What is the root cause of all these problems? - the unwritten rule that managers are more valuable than workers. If you are more valuable to the company, more money and power is made at your disposal. When your team's productivity is down, the less vauable workers will be axed rather than you. You do not have to fear the wrath of your boss, since he is also a manager and lives by the same unwritten rule. Smart people around you get the memo and decide to ditch the technical in favor of climbing the management ladder.

Is this unwritten rule valid? It may have made sense in a blue collar economy where brain ruled over brawn. But in today's world, the products are infinitely more sophisticated and the workers much more educated. A single manager cannot hope to understand all the nitty-gritty details any better than the average worker. Thus pissing off a talented worker is no longer a good idea. Before you know it, he may start a company or move to a competitor.

How should the company be organized to take this into account? How can you as a manager help? I will talk about these in a subsequent post.

Delight

I am a bit of a grumbler. I constantly complain about the sad plight of the world, software design, management and all other things under the sun. It is no wonder that people thus mistake me to be a pessimist. But oddly enough, I consider myself to be an optimist who takes pleasure in the little things of life. Here is my advice to all those who chase big happy moments - those are few and far in between and you run the risk of missing out on all the little ones. It is like Robert Pirsig said - "The truth knocks on the door and you say, "Go away, I'm looking for the truth," and so it goes away".

Recently Amish pointed me to J. B. Priestley's Delight, a collection of essays on all those things that delighted the author. Although it was written about 60 years ago, most of the ideas still resonate. For e.g. finding joy in getting an idea, meeting a friend or walking in the woods. I delight in having friends who have introduced me to new books and ideas - Thanks to Cao for SlickEdit, Feedly and countless discussions, Steve for public speaking tips, Amish for book suggestions, Yoga for philosophy, Arin for mathematics and politics, and my wife for Toastmasters and this blog.

And to top it all, in the realization that we could all be dead. Instead, here we are in this world, free to do whatever we want. Isn't that the biggest delight of them all?

Christmas Carol

I have been a fan of Savatage ever since I heard Christmas Eve/Sarajevo. This song is from the album "Christmas Eve And Other Stories" and it tells the story of an angel sent from heaven on 

"A mission from God, to find out the worth
Of everything that His children had done
Since that winter night, the birth of His son"

For this Christmas, I hope you listen to the touching tale of the Old City Bar.

"In an old city bar 
That is never too far 
From the places that gather 
The dreams that have been 

In the safety of night 
With its old neon light 
It beckons to strangers 
And they always come in 

And the snow it was falling 
The neon was calling 
The music was low 
And the night 
Christmas Eve 

And here was the danger 
That even with strangers 
Inside of this night 
It's easier to believe 

Then the door opened wide 
And a child came inside 
That no one in the bar 
Had seen there before 

And he asked did we know 
That outside in the snow 
That someone was lost 
Standing outside our door 

Then the bartender gazed 
Through the smoke and the haze 
Through the window and ice 
To a corner streetlight 

Where standing alone 
By a broken pay phone 
Was a girl the child said 
Could no longer get home 

And the snow it was falling 
The neon was calling 
The bartender turned 
And said, not that I care 
But how would you know this? 
The child said I've noticed 
If one could be home 
They'd be all ready there 

Then the bartender came out from behind the bar 
And in all of his life he was never that far 
And he did something else that he thought no one saw 
When he took all the cash from the register draw 

Then he followed the child to the girl cross the street 
And we watched from the bar as they started to speak 
Then he called for a cab and he said J.F.K. 
Put the girl in the cab and the cab drove away 
And we saw in his hand 
That the cash was all gone 
From the light that she had wished upon 

If you want to arrange it 
This world you can change it 
If we could somehow make this 
Christmas thing last 

By helping a neighbor 
Or even a stranger 
And to know who needs help 
You need only just ask 

Then he looked for the child 
But the child wasn't there 
Just the wind and the snow 
Waltzing dreams through the air 

So he walked back inside 
Somehow different I think 
For the rest of the night 
No one paid for a drink 

And the cynics will say 
That some neighborhood kid 
Wandered in on some bums 
In the world where they hid 

But they weren't there 
So they couldn't see 
By an old neon star 
On that night, Christmas Eve 

When the snow it was falling 
The neon was calling 
And in case you should wonder 
In case you should care 

Why we're on our own 
Never went home 
On that night of all nights 
We were already there "

 

 

A Deeper Malaise

I met my friend Arin at the local Starbucks. His father who had been ill for quite some time, passed away recently. The last time I asked, he was battling stomach complications introduced as a result of an antibiotics treatment. So it was a surprise to me that the cause of death was attributed to Alzheimer's! What was going on? Apparently the geniuses at the Calcutta hospital had mistaken Arin's father's disorientation for Alzheimer's and then refused to treat the stomach complications. 

Arin is however resigned to his fate and will not be suing the hospital. This is a sad example of public policy failures impinging on the individual's safety and wellbeing. Calcutta and the West Bengal state has been in the spotlight for a number of medical scandals whether it be infant deaths or a deadly hospital fire. Rather than being restricted to a handful of doctors or hospitals, the malaise runs deeper. India's creaking and often nonfunctional legal system ensures that complainants will have to wait for decades to get a favorable judgement. Errant doctors and hospitals thus go unpunished. The remaining few good ones soon realize that they cannot compete with the bad apples in profitability. After all the bad guys do not have to invest in good facilities or fire safety systems. The environment thus ends up weeding out the good ones and propagating the bad ones.

Then one fine day all hell breaks loose. Fingers are pointed at all directions. The politicians shed crocodile tears over the sad state of affairs. The legal fraternity does their bit by beating their chests. Never mind the fact it is precisely these lawyers who delay justice by repeatedly seeking case adjournments. And so the circus goes on while innocents like Arin are fed to the lions. 

 

Sticking it to the Man

The customer is king in America. Well almost always.. cellphone and Internet providers remain the last bastions of customer unfriendliness. I am pretty old fashioned when it comes to cell phones. I use my phone just as a phone. I don't want it to sing songs, take pictures or cook me dinner. Phone companies hate me since I don't contribute much to their profit margin.

The feeling is mutual. My Verizon contract expired almost two years ago and I have been unwilling to sign another one. And then the inevitable happened - I lost my cellphone. So I went ahead and ordered an unlocked Blackberry Pearl from Amazon. I was feeling pretty smug when I walked into the Verizon store. After all I had shelled out a mere $35 for a Blackberry. Alas.. Verizon considers all Blackberry phones as smart phones. So here was a chance to lure me in - a data plan for an additional $25 will be required to just use my new phone. If I didn't like the deal, I was always welcome to buy the non-smart phones from their store for a paltry $200! My only other option was to switch to another carrier. However there was no guarantee that I would get to retain my old number or get a better cellphone plan.

That is when I decided to do some research. I found out that PagePlus Cellular runs a prepaid service using the Verizon network. I called their customer service and ported my existing Verizon number to PagePlus. This took less than 30 minutes. I then provided them with my Blackberry Pearl's MEID (obtained by pressing Blackberry button > Options > Status) and transferred my number to the new phone. My prepaid plan amounts to just $100 for 1000 minutes. Compare that to the $46 I paid monthly to Verizon.

All in all, a good way to stick it to the Verizon Man. 

Toastmasters Speech #8 - In Praise of Idleness

Toastmasters speech #8 emphasizes the use of visual aids for communication. I decided to follow the Presentation Zen approach by having 5 slides with only pictures and no dreaded bullets. This speech was inspired by Betrand Russel's essay of the same name.

Let me start by transporting you back in time. The date is 326 BC and Alexander the Great has reached the banks of river Sindhu as part of his conquests. On the banks of the river, Alexander comes across a gymnosophist, a naked yogi who is sitting on a rock and meditating. Alexander's curiosity is piqued and he asks the gymnosophist - "What are you doing?" and he replies "I am doing nothing". The gymnosophist then asks Alexander - "What are you doing?" and Alexander replies "I am busy conquering the world!" They both laugh thinking "What a waste of life!"

I am sure that many of us here can sympathize with Alexander. America was built by pioneers who were energized by the Protestant work ethic. Work was indeed considered virtuous. We even have proverbs for it - "Work is Worship", "An Idle Mind is the Devil's Workshop". Even today, America has the shortest vacation in the world. And every year, Americans end up working more and taking lesser vacations. 

When I was young, I used to think that all the busy people were important people. After all, why else would they be busy? This even leads a lot of people to feign busyness. Soon you find yourself invited to attend hundreds of inane meetings where one talking head goes blah, blah, blah. But are we really achieving anything here? I would say being busy does not mean being important. Instead it means being time poor. How would you feel if a beggar accosted you on the road asking for a dollar. You will have pity towards him.. After all he is lacking money. But Time is the most precious resource of them all. If you lose it, you can never get it back. Shouldn't you then be feeling sorry for all the busy people, frittering their lives in countless meetings?

And that brings us to the fundamental question - Why do we work? Let me throw some numbers here. In the 19th century, people in Victorian England used to work about 15 hours per day. You couldn't blame them. Ever since the dawn of civilization, everyone in the family had to work all their waking hours to bring food to the table. But since the Industrial Revolution, science and technology has revolutionized how we do agriculture. We can now produce food cheaper and in much larger quantities than was ever possible in modern history. In today's world, an average family should be able to work just 4 hours per day to bring food on the table. But look around.. how many people do you see working 4 hour days? That is because we have invented a whole array of things to spend our money on besides basic necessities. 

Idleness is thus being time rich. You could be rich in time by being more effective. Maybe you are a master at delegating, delaying or even deleting work. Or maybe you have mastered the art of saying No to each and every opportunity that comes your way. However you do it, at the end of the day you have time for taking long walks in the park or hours reading the Sunday newspaper. It is at these times when you truly unwind, does your creative juices flow. We live in a world where being creative and having ideas is the single most important skill that you can possess. Menial labor can be automated or outsourced. But there still isn't a smart computer program to come up with breakthrough ideas.

Remember Alexander and the gymnosophist? A year after their meeting, Alexander's army mutinied against him and in three years he was dead. The gymnosophist laughed at Alexander because he thought the entire world conquest idea was pointless. Today, no traces of Alexander's vast empire remain. But the ideas of the gymnosophist on yoga and ephemeral world continue to influence humans everywhere. It seems the lazy gymnosophist had the last laugh.

Unconventional Wisdom

I rarely engage in political discussions especially if they pertain to Kerala. But I could not help but butt in when Bino was extolling the virtues of Oommen Chandy, Kerala's current chief minister. Mr. Chandy has been winning brownie points for his much publicized outreach efforts. These include installing a webcam in his office and holding people's durbars where aggrieved people are dispensed quick justice. Conventional wisdom thus holds that Mr. Chandy is better than his predecessor. But is that true?

Humans are particularly vulnerable to the Messiah effect - the notion that One will rise from the multitude, take charge of human affairs and right whatever is wrong with the world. Notice the emphasis on the singular. We are more comfortable in suspending disbelief when it comes to a single person rather than a group of individuals. Maybe this is a remnant of our tribal psyche where everyone in the tribe had to pledge allegiance to the Chief or else. But our current world is a more complicated animal where the wisdom of yore no longer holds true. 7 billion people pose a different set of control problems - How do you organize them in a scalable fashion? How will you ensure resiliency? Who is in charge of the transfer of power?

India is a functioning democracy albeit a creaking one. As every year 17 million people are added to the national roll, the government needs to reinvent itself to stay effective. One way to do this is by decentralizing power by creating local governments and then empowering them by providing resources. The former has been implemented in Kerala via the panchayat system. However the latter has never been carried out effectively due to the intransigence of successive state governments including those headed by Mr. Chandy. Since the panchayats were not given enough money or power, all decisions are still being made by state governments. So if you need to fix your local roads or libraries, you will need to tolerate the whims and fancies of the bigwigs at Thiruvananthapuram rather than contacting your local panchayat member. Naturally this leads to a situation where the state government becomes a bottleneck as 35 million citizens clamor for its attention.

Conventional wisdom is thus false - adding a webcam or holding people's durbars does not make Mr. Chandy our Mahabali. He should instead concentrate his energies on systemic reforms that address the real problems. So the next time someone dishes out conventional wisdom, think it through before digesting it wholesale. The wise person should always ask these two questions - Why do I believe what I believe? How do I know what I know?