Abhiramusings

Indian Cricket: My Views

2011-03-24T09:56:00.008+05:30

The Indian Cricket Team did not lose to South Africa because Dhoni gave Nehra the final over. They did not lose because the middle order fell very quickly. They lost because Gautam Gambhir failed to give enough strike to Sachin when they were batting together. Often, there would be spells where Gambhir hogged most of the strike, but scored at low rates. With Sachin at the other end, and that too in the mood, it was undesirable for reasons anyone can enumerate. This caused Sachin to play a rash shot, and be dismissed. If not, Sachin would have been under lesser pressure and India would have easily scored at least 30-40 runs more.

Coming to my main point - Often, the Indian public's reaction to the cricket team's losses are both shallow and unsavoury. Just because Dhoni has not scored big over the past year, it does not mean marriage has caused him to lose focus. Just because the middle order falls cheaply once in a while, it does not mean the batsmen are making too much money from advertisements. And just because there are times when Sachin is the only batsman who bats well, it does not mean he is carrying the team on his own.

I don't blame Gambhir for not scoring quickly. Simply put, no Indian batsman can match the exalted batting abilities of Sachin. The class of the man is evident; the same ball that Gambhir finds hard to hit, Sachin hits it for a four. That said, we must not forget that a lot of the cricket team's greatest victories have been in matches where he has not particularly done well. The Indian Cricket team is comprised of fantastic crickets, very diverse and very talented. From Yuvraj's charm to Laxman's genius, from Zaheer's accuracy to Bhajji's guile, we are lucky to have a team like that. And enough has been said about Sachin; watching him bat is like watching Zidane or Ronaldo (the Brazilian, NOT THE PORTUGUESE) with the ball at their feet. It is an absolute honour to have been able to watch him all these years.

I love the cricket team and I am very proud of them. We must learn to savour their triumphs more than complain about the failures. They won following on! They beat Australia so many times, and in such emphatic ways. They have beaten Pakistan whenever it was really important. They beat SA having scored just 194. Why?! Why do we forget these and only dwell upon recent failures?

On a deeper note, why are we so bothered about their prowess really? Why do we attach our self-worth to their success? After all, India beating Australia does not mean it is a better country than Australia. Why then are we so bothered? It is not Dhoni's fault that he makes millions with advertisement money!

We must learn to appreciate them and enjoy their victories and ignore the losses. We must avoid making flippant comments like "They don't bowl yorkers in the final overs" or "There is no good team spirit because they earn too much money", it simply makes no sense whatsoever.

It is this Abrahamovic-ish (Chelsea owner) attitude that has caused us to lose a lot of very talented cricketers over the years. One that stands out, for me at least, is Hrishikesh Kanitkar. I really liked this guy, and I strongly believe he would have done great for our team. Him and a lot of other people lost their place in the team and were never given a second chance. One must realise that team-selection can never be an exact science; there is always a bit of a gamble, the perform-or-get-thrown-out attitude is extremely unhelpful.

The team is being run by people with far more cricketing knowledge than we have, must be place our trust in them and not view everything they do superficially. It is extremely hard to manage the team, given that the public has such high expectations. The least we can do is to be less-critical.

It has always been a dear wish of mine to see the cricket team win a world cup. Aside from sending positive thoughts, there is nothing that I can do. I do hope for the best from today's match. Having said that, I will not let a defeat affect my mood. I am and will always be proud of our team and will always be a proud spectator to their progress. Good luck team India.

P.S. - I think Sachin's best innings, and the best innings I have ever seen was his 136 against Pakistan in Chennai

Letter to a 10 year old Abhiram

2010-12-14T16:04:00.006+05:30

Dear 10 year old Abhiram,

Hope you are well.

Very recently, I was wondering what it was like to be you. I contrasted my current situation (goals, priorities, responsibilities, etc) with what they must be for you and I have come to the conclusion that I am far cooler than you. This letter is to rub your face in it.

Look around you. You are probably surrounded by a lot of stupid friends, just like you, happily playing silly games like hide-and-seek, chor-police and what not. Life probably seems great to you. No big decisions to make, no interviews to take, no advisors to answer... Your only worries are your final exams and whether or not you will pass them. You probably read articles of people reminiscing their childhood with great pleasure, telling yourself that you are actually living their dream. Let me tell you something, life is far more awesome than what you make of it now, and I am getting to see it.

You know what, I don't have to be back at home after 6. I can drive, legally. The same parents you have, who give you instructions on how to cross a busy road, now go to the extent of trusting me with amounts of money you can't even say in one breath. At public gatherings, adults don't just make nonsense small talk with me like - which class are you studying in, which subject do you like the most; they treat me like an equal. I understand and do math that you don't even know exists. I don't have to study history and geography like you do. I know what it feels like to have money of my own and decide what I want to spend it on. Your parents, whom you turn to for everything, now turn to me for quite a few things. I get to travel alone. And you know that thing you heard of called a computer - I own one today. I will not even begin to go into what all it can do, you will only think I am lying. You know something even better, I can even make it do things. I get marks for studying it well.

I understand the world far better than you do. Those college graduates who make you stop playing cricket just so that they can play, I AM ONE OF THEM! To top it all, I know all that is going to happen to you in your next 13 years. Don't worry, nothing too bad will happen :)

Yes, the bad news is you are not living anyone's dream; in fact, I am living your secret dream. But you know what, you are going to have all that I have now. And once you grow older than me, you will have even more and can even make fun of me.

I write this letter, not to mock you, but to advise you to concentrate on the present and fully enjoy it. That is all you have in your hand. There are things in your present you have never had nor will ever have again. Not that you will miss them; but you better enjoy whatever you have right now, rather than thinking about what you had when you were younger or what you can have when you are older. That way you will have had fun at every point in life. God bless you.

Yours affectionately,

23 year old Abhiram.

P.S. - The Indian cricket team has still not won a world cup. I am waiting for it too.

Aisha - Movie Review

2010-08-22T09:35:00.008+05:30

Normally, I stay away from movie and restaurant reviews. But Aisha was so quick to take second spot in my personal "worst movies ever watched" list that I thought a post was warranted.

Yes, Aisha occupies second spot in my list. And this is coming from someone who has watched, inter alia, movies like (a) Tushar Kapoor starrer "Kuchh to Hain" (b) Thoda Pyar Thoda Magic - Saif Ali Khan and Rani Mukherjee (c) Golmaal Returns.

My entire Aisha experience was like a root canal session. The story is decent, the supporting actors are decent, but Sonam Kapoor, like a true father's daughter, ruined an otherwise destined-to-be-nice movie. She is good-looking as well as hot, no doubt. Sadly, that does not mean you are allowed to be unbearable on all other fronts.

She needs to attend an acting school where they teach more than two expressions - one and two (closest matches I could find on the internet). In addition to that, she needs fake accent training either from Priyanka Chopra (example) or Freida Pinto (example). Aisha was a forgettable experience. I suggest you stay away from it.

Things Money Can't Buy

2010-08-16T04:59:00.017+05:30

Return trip from Boston to Bangalore - $12xx

Cab ride from bus-stop to department and back (because I had forgotten to take printouts of tickets) - $10

Change Charges on ticket to fly directly to Frankfurt from Boston, instead of going through Toronto (because I did not have a Canadian Visa) - $120

Food at Frankfurt Airport - $9

Ride from BLR Airport to home - $15

Expressions of surprise (they did not know I was coming) on the faces of loved ones - Priceless

Leads to the following question: Do all priceless things have a price?

Examples in favour of the argument: Look at the mastercard advertisement. The camera costed some money, and a photograph with "five generations in it" could be taken only because they had the camera. Also, the advertisement where the parents spend money on expensive toys for their kid and the kid plays with the packing box instead of the toys - the parents found that priceless only because they realised how paying money cannot make a kid happy. If they had not purchased toys and found the kid playing with a random box, they would have simply thought "stupid kid" (peddu mundedu in Kannada).

P.S. - Thanks to S for helping with the arragements.

8 Hours of Sleep

2010-07-18T08:57:00.028+05:30

I often get forwards telling me how sleep-deprivation is dangerous and why 8 hours of sleep is mandatory. They specifically say how sleep-deprivation decreases your productivity. Obvious yes, but I wanted to take a mathematical look at the problem and remove all doubts.

Disclaimer: Questionable Assumptions, Flippant Arguments

I shall assume we take, on work days, an average of 6 hours for (in no particular order): Travelling, Bathing, Eating, Dressing, Cleaning, Ablutions, Chatting, Waiting (ex:- waiting for facebook to load photo albums, waiting for some &*^#%s reply on gchat), Searching (ex:- keys, spectacles, wallet), and tons of other worthless things. These are things we HAVE to do. Although I do know that the actual amount of time we collectively spend on these things could vary heavily, I think 6 hours as an average value is a reasonable assumption (obviously not valid on weekends).

This leaves us with 18 hours in a day for mental-health and work. I shall also assume that we should aim to maximize overall-benefit and that it is partially explained by the equation: $overallBenefit \propto output_{work} * mentalHealth$. Further, I take $output_{work} \propto f_1(x)$ and $mentalHealth \propto f_2(y)$, where $x$ is amount of work time and $y$ is amount of time spent for mental-health, both in hours, with the equation $x + y = 18$ holding good.

Lemma 1: $f_1(x) = 1-2^{-x}$

Proof: I decided, for $f_1$, an exponential function of x would be best and that polynomial and logarithmic functions of x did not make sense for some reason. And according to Abhiram (2009), 2 would be a wise choice for the radix. $2^x$ would be in $[1,\infty)$ when $\usepackage{amssymb} x \in \mathbb{R}_{\geq 0}$. I take the reciprocal of it to force its range to be $(0,1]$. Now, to make it an increasing function, I subtract it from 1. qed

Lemma 2: Lemma 1 is not total nonsense.

Proof: A plot of $1-2^{-x}$ looks like this.

This shows that there is a sharp increase in output initially and that it plateaus after a while. Kind of makes sense. qed

Lemma 3: $f_2(y) = log(y)$

Proof: We would once again need an increasing function of y. In general, spending twice the amount of time you are already spending on mental health cannot increase $f_2$ by a factor of 2. Thus we would need to attenuate y. Given this, and some other considerations, a logarithmic function was the only thing that made sense. qed

By Lemma 1, 2 and 3, we have

$overall-benefit = f(x) \propto log(18-x) * (1-2^{-x})$.

The plot of $f(x)$ versus $x$ looks like this.

Deduction: Maximum benefit is achieved by working for 6 hours, i.e. $x=6$ is the optimum.

This leaves us with 12 hours for mental-health. Of course, using all that for sleep would not be wise, because sleep is not the only thing that influences mental-health. General reading, playing, music, praying.... and a tons of other things could and probably SHOULD be done! Catching up with news, making small-talk..... Helping your computer-illiterate neighbours setup their video cam is also not a bad idea. It buys you good-will, which can sometimes enhance overall-benefit all by itself. I shall assume an average of 3.5 hours for all this. This, and half an hour everyday for latency (various things...) gives us 8 hours of sleep!

P.S. Read this manual sometime if you can, it is about how you get the maximum out of your sleep.

Flight to Infinity

2010-06-13T08:32:00.021+05:30

Two trains start 20 miles apart and head toward each other, each going at a steady speed of 10 m.p.h. At the same time, a bird that travels at a steady 15 m.p.h. starts from the front of the first train and flies to the front of the second one, and then turns around and flies to the front of the first train again, and continues in this manner till the trains meet.

Questions:-

(1) How much distance will the bird cover before the trains meet?

(2) How many trips will the bird make?

Question 1 is easy. The relative speed between the two trains is 20 mph. So they meet after $\frac{20}{20} = 1$ hour. The bird would have travelled $15 * 1 = 15$ miles.

Question 2 however is not so simple. Consider that the trains are $x$ miles apart. The bird takes $\frac{x}{15 + 10}$ hours to make a trip. The distance between the trains reduces to $x - \left(2 * 10 * \frac{x}{25}\right) = \frac{x}{5}$ miles. This means that one trip of the bird reduces the distance between the trains to one-fifth. Given that the trains start 20 miles apart, we can say the distance between the trains after $t$ trips of the bird would be $\frac{20}{5^t}$. Thus we get the total number of trips of the bird as $T$:

$\frac{20}{5^T} = 0 \Rightarrow T = \infty$

The answer, though mathematically logical and valid, is a little hard to digest. At least I found it so. How can a bird make infinite trips? Bicyclists, flies, speed.. all seem so real and yet the answer seems so detached from reality. The trains meet in finite time, the bird travels a finite distance (answer of question 1) and yet the bird seems to have made infinite trips... How can infinity exist within things that are seemingly finite?

Infinity is a hard concept to understand and feel. I will not claim to have understood it. I have just made my peace with it. I do however seem to have an explanation as to how this seemingly realistic problem transcends to the unreal. When I say "seemingly realistic", I mean that it is perfectly possible to have trains which travel at constant speed and birds which fly at constant speed. By unreal, I am referring to how hard it is to believe that a bird can make infinite trips.

Although the speeds and situations are realistic, it is impossible to have a bird which touches a train and turns back immediately. The problem assumes that, if the bird is perched on a train at time $t$, it is in flight at times $t - \epsilon$ and $t + \epsilon$, for all $\epsilon > 0$. This is exactly where it moves to the unreal.

However, if we did consider the bird to take even a minimal, but non-zero, time to switch between the trains (say $\lambda$), we would have - bird takes $\frac{x}{25} + \lambda$ hours to make a trip. Thus one trip of the bird would reduce the distance between the trains to $\frac{x}{5} - 20 \times \lambda$. Obviously, then, we would have a finite number of trips.

Coming back to the concept of infinity, it is hard to feel it. The best you can do is have a fleeting image of it when you close your eyes and imagine the universe. A mosquito itch on your knee immediately brings you back to your sad room lit with fluorescent light. I end with this exquisite quote by Jacob Bernoulli

... Even as the finite encloses an infinite series

And in the unlimited limits appear,

So the soul of immensity dwells in minuta

And in the narrowest limits, no limits inhere

What joy to discern the minute in infinity!

The vast to perceive in the small, what Divinity ...

LATEX Works on Blogspot!

2010-06-11T02:34:00.023+05:30

Today I chanced upon a webpage which had instructions on how one could enable LATEX on blogspot, and write stuff like $\LaTeX$, $\frac{1}{2}$, $\mathcal{P}^r(\mathcal{L})$ or even:

\[ \frac{numerator1}{denominator1 + \frac{numerator2}{denominator2 + \frac{numerator3}{denominator3}}} \]
Needless to say, I am pretty excited.

Edit: The link with the instructions seems to be down. However, following these instructions will have latex working on your blog.

(1) Copy the piece of code below and paste it in a "HTML/Javascript" blogger box.

(2) Type latex code between $ signs.

(3) Publish the post.

(4) Behold and enjoy.

"Probably" Wrong

2010-06-09T05:54:00.014+05:30

If you are writing a program involving probabilities and it is buggy, you would first check if you are getting your probabilities right. The primary thing you would do would be to ensure that for all p: $0 \le p \le 1$

It has been two semesters here at Brown for me and the highest wrong probability I ever got was 3.5. Today, however, I broke the boundaries and achieved a probability of 237.56, my personal best by a whopping margin. Given that I find nearly a 6500% increase over my previous best, I could not resist sharing my success.

I dedicate my success to hours of game-playing and not-doing anything, which in turn forces me to do things in such a hurry that I end up with state-of-art results.

Gtalk Etiquette

2010-03-19T18:53:00.012+05:30

When in the middle of an online chat, I get extremely pissed off if I have to wait more than 20 seconds to get each reply. Yes, the other person might be doing something important and I might be interrupting, but I expect to be told that so I don't wait staring at the chat window waiting for a reply. If you are available, i.e. green, and you are in the middle of a conversation with me, I expect you to give replies instantaneously.

In a face-to-face conversation, you would need to give undivided attention to the person you are talking to. It would be inappropriate to do anything else mentally/physically involving when in the middle of the conversation. It would be inappropriate to talk to a third person in between too. The dynamics of an online conversation are clearly different. The thing that makes online conversations different is the delay in transmission of messages. It would be a waste of time to do nothing other than chat with one person. In the time between the instant you send your message and the instant you receive the reply, you could and should do something else. This will help minimize your idle time.

However, your idle time is not the singular most important thing. On the other side is a human being, whose time is just as valuable as yours, irrespective of who you are! Keeping this in mind, I have set myself some rules which I faithfully stick to all the time.

(1) As soon as I log into gmail, I assess my status. Am I free to talk to people? If yes, I am green (available). If not, I assess how busy I am. If I am busy enough to be unable to give pingers undivided attention, but free enough that I would like to hear if someone has something interesting or important, I am red (busy). If I just do not want anyone to bother me whatever happens, I am invisible. Further still, if I do not want the rare event of someone taking the chance and pinging me even when I show as offline (hoping I am invisible), I sign out of chat.

(2) If I am busy/invisible and someone pings me, there is no pressure on me to reply. I am allowed to take my time. I need not even reply in the near future. It is their problem they pinged me in spite of me not being green.

(3) If I am green, and someone pings me, I try to reply as soon as I can. If it is longer than some amount of time, I shoot a "sorry, was not at desk". This is w.r.t. the first reply.

***(4) With subsequent replies I make it a point to reply INSTANTANEOUSLY (when I am green)! The only delay the other person should face with each reply should be time_taken_for_message_to_reach_me + my_thinking_time + typing_time + time_taken_for_travel_of_message + epsilon. If I cannot reply instantaneously, I make sure the other person knows I am doing something else. Once again, if I am red, all this is not necessary. I can take my time for each reply.

(5) If I violate any of the above, I apologise sincerely, irrespective of who the other person is.

NOTE:- If I have violated any of the above 5 with you, it will be because you have violated one or more of points (1)-(5), OFTEN.

I have a low opinion of anyone who grossly violates points (1)-(5) (okay once in a while). Who am I to make rules and make judgments you ask? I am no one. It is unlikely that I head a multi-billion-dollar company in the immediate future and hence you really need not be nice to me. However, do not expect me to be nice to you either. If you make me wait for every reply I need to get from you, be prepared to face the same thing.

Having rules for online chatting seems too prudish. Online chatting is informal and I want it to remain that way. However, one must keep in mind that on the other side is a human being, whose every second is as valuable as yours. It is about respect and value for others time, and about valuing it as much as you value yours. It is easy to be respectful towards your professors, your managers, your elders. Being respectful to them reflects nothing about your character. You respect them because you are the one who loses if you don't. The fact that you respect them only means you are not stupid, and that is not much. How much you respect your equals (your friends, loved ones, etc) and people below you is what counts. Watching youtube videos or reading articles when in the middle of a conversation is plain rude. If you still want to do it, just let the other person know that you are doing. That is the least you can do.

I swear to god that this post is not aimed at anyone. I hope and I do believe that my friends and the people I care about do not undervalue my time. Everyone is nice to me. I write this post just to float the idea that it is not just your time that is important.

As always, I have a CS analogy for this. You are a CPU. The way you respond to people pinging you reflects the job scheduling algorithm you are running. The people pinging you are the jobs that request the CPU. You try to maximize the throughput, i.e. minimize CPU idle time. The time taken for your message to travel to the destination and for the reply to come back is akin to jobs waiting for an I/O resources. I think it is best you run a mix of round-robin-scheduling and first-come-first-serve. And even with round-robin scheduling, have an upper limit on the number of jobs you schedule. You should determine the upper limit for yourself, depends on your typing speed and other stuff. There is something slightly different here though. Minimizing job starvation time (time spent by second person waiting for your replies) is almost as important as minimizing CPU idle time (your idle time). The importance ratio is what reflects your character. Let us define:

importance_ratio = importance_of_second_person's_time / importance_of_your_time

You are free to set it to whatever you want. If you set it to 0, you are an arrogant bastard. If you set it to infinity, you are a noble idiot. 0.9 to 1.0 would be best I think.

Movies vs Books

2010-01-28T06:51:00.005+05:30

Just yesterday I heard my friend say he only watched movies and never read books (apart from academic ones). He even argued that there is nothing you can get from a book that a movie or a documentary does not give you. He believed that as an artist, expressing yourself using video would be easier and more liberating than text. And better means of expression meant that you convey more and in a better way, hence the receiver would be more enriched when they watch video. Though I could not summon an argument right there, below is my rebuttal.

Technically the information available in a book could be reproduced in any kind of video medium, maybe even in more splendour. However, the take home from a book reading is not just what the author wants to say, it is also what you make of it. Personally, when I see things in text, it gives me the freedom to make my own pictures and audio. I absorb it into my fantasy world, which is far more beautiful than what any video medium can show. I shall quote Aamir Khan from Taare Zameen Par - "...the table is too weak to hold the burden of your imagination...", in response to a kid asking him why there was no model on the table for him to imitate while painting. In this context I mean to say that 2-D TV and Dolby Digital are far too limited to portray what your thoughts can show you. And the exercise of making a picture out of text is crucial and probably far more enriching than directly having the pictures spoon-fed. Waiting to hear people's thoughts...

I think...

2010-01-10T04:20:00.013+05:30

Often, I say I like/hate something just because everyone around me likes/hates it; just to "fit in" socially... Everyone does that. The compelling reason for this post is that I recently found myself in such a situation and felt awful that I lacked the courage to be frank. Here goes...

(1) Shaan is a terrible singer and Tanha Dil is an ordinary song

(2) "The Shawshank Redemption" is not a great movie

(3) Black, Rang De Basanti, Slumdog Millionaire, (many more, this is all I can remember right now) sucked

(4) Other than Lisa Kudrow (Phoebe of Friends) and Kajol, most women cannot do comedy

(5) Ricky Ponting should break all of Sachin's records

(6) MS Office is the coolest piece of software written; Windows is cool and so is Bill Gates - This is taboo, coming from a CS guy. You are trained and brainwashed to hate windows and everything related to it

(7) Richard Stallman's rants are unbecoming of someone of his stature

(8) George W Bush and Manmohan Singh are cute

(9) Irrfan Khan is not a great actor

(10) Russel Peters is not funny

(11) Harsha Bhogle is neither smart nor insightful.

(12) Black Forest cake sucks

(13) The Backstreet Boys are awesome

(14) Rock (music) sucks

(15) It is hard to decide which among twitter and facebook is more lame

Footballer of the Decade

2010-01-06T10:51:00.024+05:30

Yes, you are right, the high frequency of posting is because I have holidays.

This post is inspired by the footballer of the decade poll that is being conducted on espnstar.com.

Inclusions in the list that I disagree with:

1. Christiano Ronaldo
They might have as well included Baichang Bhutia!!! Christiano is fast and has deadly shot power. But that is not enough qualification to be on the footballer of the decade list!. If he is there, why is Messi absent? I do not see any difference between them. It is just recent hype and the fact that Real Madrid were stupid enough to spend on him almost twice the amount they spent on Zidane. I sincerely hope he does not win!

2. John Terry
Fantastic footballer. But still does not deserve a nomination for this title. For me every nomination should have something extra-ordinary that makes you say "wow! no one can do that like he does". John Terry is not one like that.

3. Eto'O
Once again, far from extra-ordinary. In fact, does not have anything special according to me. He scored a lot of goals only because he was surrounded by the likes of Ronaldinho and Messi. Another guy who has succesfully fooled the world into believing he is good just because he scores a lot (remember Ruud Van Nistelrooy). I am sorry, but I cannot write any soccer post without making fun of Van Nistelrooy.

4. Raul
Good, but I see so many better ones who could have been there, Rivaldo, Ronaldo (the Brazilian), Bergkamp, the list goes on.

Exclusions that make my heart ache:

1. David Beckham
Yes, he does not have the best history. But give me just "one" footballer who is a better free-kick taker than him. He was a great shot too.

2. Ronaldo (Brazilian)
He is the phenomenen! The most scintillating footballer of the decade. At his best, he could beat 5 defenders and score! God knows how Eto and Raul were chosen over him.

3. Roberto Carlos
Not that he is better than any of the defenders currently on the list, but I think we should have a specialist "left-back". I know Maldini could fill in for that position. But I say he should have been there instead of Terry. After all, the previous decade saw him win a Champions League as well as a World Cup.

Some others- Dennis Bergkamp, Roy Keane, Rivaldo... I know some of the footballers I have talked about were well past their prime in this decade, but I still believe the list should have had them.

I shall now make up my "dream team" from the last decade. There are many ways you can make up a dream team. It is all about perspective...
(1) Taking the biggest names in each position, and not worrying whether they can play with the others in the team
(2) Choosing people always thinking that they have to "play with each other". So you choose people wanting to build a complete team.

I shall do it the 2nd way. Below is my team. Total Football will be used, at least among the midfielders and the forwards. Everyone is responsible for both defence as well as attack.

Fabien Barthez (GK): A maverick. But still unbeatable when in the mood. Buffon, Casillas, etc might be more reliable but I consider Fabien the best shot-stopper. And given the technical defenders, he would add some craziness to the otherwise boring defence.

Lilian Thuram (RB): Nothing to say, picks himself.

Maldini (CB): Nothing to say.

Nesta (CB): Considered a lot of other people for this position, but thought he would gel best with Maldini, given that they played together.

Roberto Carlos (LB): Would add to the adventurousness of the defence, just like Barthez. A very capable defender and probably the most powerful kicker of the football. Would help behead an opponent with his kick.

Roy Keane (CDM): Captain of the team. Given the attacking formation and the general nature of the other players, he would help hold the midfield together.

David Beckham (RM): Natural Choice. Would be the primary freekick taker and corner man too.

Solksjaer (CM): A weird choice I know. Reason for choosing - the team is composed of stars. Stars have a tendency to collectively fail on a single day. Ole would help rescue the team on such a day. There are a lot of people who can fit this description, but what to do, Manchester United bias you see :)

Zinedine Zidane (LM): Nothing to say. A true GOD!

Ronaldo Luiz Nazario (LF): Not the idiotic Portuguese, the Brazilian. The most devastating striker I have ever seen. Was unstoppable at his peak.

Wayne Rooney (RF): Another choice I need to explain. The attack is largely composed of high maintenance flair players (Zidane, Beckham, Ronaldo...). Rooney has always shown to be willing to run back and do a bit of defending. This is again an attempt to balance the team, with a strong Manchester United bias ;)

And last, definitely not the least, the most important guy, i.e. the manager/coach.
My pick for footballer of the decade. Zinedine Zidane. I do not say "God" for all and sundry. But this guy truly was. He made soccer look easy. He always looked to be playing in slow motion. Perfectly economical and optimal movements with mesmerising skill and control of the ball. Though I have not seen any footage of Pele, Maredona, I would say he is the best footballer ever. Maybe not w.r.t goal scoring, but for sheer class and finesse. Below is a video of him. Watch it and you will know why I love him so much.

New Look

2010-01-05T13:37:00.007+05:30

If you were hoping I got myself a new look, I am sorry to dissapoint you. It is my blog. If you want more such beautiful templates, go here. The procedure to change the template is given here. Good luck. And I would be extremely grateful if you can comment whether you like this new template or not. Specifically, I want to know whether it is pleasing to the eye. Thanks in anticipation.

Why AI Failed - My Two Cents

2009-11-28T10:57:00.021+05:30

This post is inspired by the late Dr. Push Singh's article titled "Why AI Failed". When I say "failure" of AI, I am referring to the fact that we still do not have machines with human-level intelligence. Such machines were expected by 2001 itself. We know that science is not even on the brink of it. Dr. Singh's article is comprehensive and succinct in its explanation. In this post, I talk about the same thing with an analogy. In the analogy, I shall describe a problem and analyze two possible methods of approach. I shall end by drawing parallels and explain what is going wrong, in my opinion, with the current direction of AI research.

Before I detail the task, there are somethings I would like to say. The task I am going to talk about is an "ideal" case. It cannot be reproduced in real life. When I use terms like examination, please do not form a vision of a silent hall with an invigilator and a time limit of 3 hours. The whole thing is totally abstract. Analyze this article from 50 feet above - think about everything in general, do not nitpick and confine yourself to the material words I use. They are just there to make this article take a form in English. In fact, I myself do not have concrete pictures about what I am say. Think of this post as a description of something I see far away without my spectacles on!

The task - We are to train a 10 year old in mathematics and make him fit for an exam in integral calculus. Details are as follows:-
(1) You are God! You are perfect. Once again, Please do not think of God as a magician with a halo around his head who can do anything. I just mean you are "ideal". You know the perfect optimal way to do and solve anything.
(2) This 10 year old that you are assigned is just an average 10 year old. Nothing extra-ordinary about him. Nothing bad about him either. He is "human".
(3) The exam is one like no other. The score you get is a "perfect" indicator of your knowledge about integral calculus. Only God(you) can get 100%. The "human" cannot. Also, knowing even the most basic and elementary formulae of integral calculus will mean that you score more than 0. Think of this exam as a compilation of the all the questions that can exist about integral calculus. Right from the most elementary and trivial ones, to the most complex ones.
(4) Your sole objective is to maximize his score in the exam. You do not care about anything else.

The first question that you would now have would be - "how much time do we have?". I am not going to given an answer to this right now. Please push that question to the back of your head. All I shall say now is that the time is not enough to turn him into a God, i.e. make him score a 100%. 100% needs "infinite" time (if you do not understand why I said "infinite" time, please think about it. Getting a vision of "ideal", "perfect", etc. is essential to proceed. Such concepts are difficult to put in words. They can only be felt). You only have "finite" time on hand. Since I say the 10 year old is average, our task at hand is not a trivial one. It will take time and careful planning. Your planning would not only involve deciding what mathematics to teach him, but also a plan of the boy's daily routine. Right from the games he plays, the food he eats, etc. It is like he is totally in your control.

I do not know the perfect solution to this problem myself. I am sure no one reading this post will either! I can say that confidently because I am talking about "ideal" cases here. The exam itself is not conceivable. (A lot of people have exagerrated views about their teaching and mathematical abilities, I myself have ;). The fact that you were good at solving integration problems in college and could do them faster than all your friends does not mean you are the "ideal" person I am talking about here. We are all equally idiotic in front of "perfection". Someone may be a 10, someone else maybe a 200, 10000, or whatever. In comparison with infinity, all of them are nothing(zero) because anything divided by infinity is zero). If you think you know the perfect solution to this problem, I suggest you stop reading the post. It is useless for you to proceed.

If you are reading this paragraph and further, you agree that you do not know the perfect solution to this problem. I don't know it either. There are a lot of approaches we can talk about. Small changes in one might cause improvements. I do not want to get into that. I just want company as I attempt to analyze the "kind" of solutions possible. Hopefully one day we will know the perfect solution. I think the approaches can be broadly categorized as below:-

Approach 1: The drilling-in approach. Since the sole objective is to maximize the score in the exam, make the kid learn as much as possible by-heart. Begin with the basic formulae. Drill them in! Remember, this will help because the "exam" has the most basic and elementary problems as well as complex problems. Get a few basic text books and make him learn all the solutions by-heart. This will also push the score higher. Keep doing such things. Make him work overtime, to the exclusion of everything else, even sleep. Think about the scores you can reach with this kind of an approach...
Approach 2: The normal approach. Draw the kid a proper routine. Start with the basics. Make sure the kid develops in all respects. Now, think about the scores you can reach with this kind of approach...

Below is the graph of scores vs time taken of both the approaches.

Note:- I do not have any real concrete reasons for why I think the graph should look like that.

Observation from the plot: If the time given is less, approach 1 will lead to better results. If time given is more, approach 2 will lead to better results. I am sure this conclusion is not counter-intuitive by any means. Basically approach 2 has a higher rate of growth after a certain period of time. Approach 1 is good if the time of reckoning is small. I don't know if either of them will reach a score of 100. But all I can say is that if they do, approach 2 will beat approach 1 to the finish line. In fact, I believe approach 1 has no hope. It will plateau after a while. Approach 2 is the only one with hope.

Let us now get back to what I wanted to talk about - AI and its failure. I think the kid is our computer, the computer scientists and programmers are the gods. The integral calculus examination is just a way to see if the computer has achieved human-level intelligence. Scientists today are using approach 1. That is because it gives "immediate" results. Grants are given with deadlines. People giving the money want to see results quickly. So they do not care how the results are obtained. I am sure if you were to apply approach 2 in real life with a kid, it would take a lot of heart and tenacity. Just like that, for computer scientists to move towards the goal of human-level intelligence using approach 2 will require a lot of courage and rigour.

It is sad to see that very very few are prepared to do that. It is this which I think is the fundamental reason for the failure of AI - our "short-sighted" (desire of immediate results) attitude. I call out to the scientific community - please broaden your minds and vision!!! Please look beyond your immediate materialistic needs. Do not forget them!!! Just look beyond them once in a while.

I am very inspired by the following people - Marvin Minsky, Chris McKinstry and Push Singh. I hardly know anything myself. In fact, my first step into the field of AI was 2-3 months ago! I know nothing! It is just that I am interested and very inspired by the idea of human-level intelligence on a computer. It is like "hacking into God's computer" - I am borrowing Chris' words. I believe computers with human-level intelligence will solve all of the worlds problems.

...subtle is the lord, but he does not play dice with the universe... My views about determinism later...

Reward = 2 * Effort

2009-09-30T05:19:00.020+05:30

As children, we are told by our parents that when we do a good deed, we get twice of what we do in return. Below is, what I think, mathematical proof of that.

T.P.T:
Reward = 2 * Effort

Assumptions:
(1) Life is an equation of the form L.H.S = R.H.S; where the LHS is the summation of all the efforts we put and RHS is the summation of what life gives back to us. Basically the = sign is put based on the assumption that we always get out of life exactly what we put into it.
(2) If we do a deed 'x', and it is good, '+x' is added to the LHS. If the deed is bad, we add a '-x' to the L.H.S.
(3) I we get a positive value on the right hand side, it is a reward. If we get a negative value, it is pain.

Proof: If a person does a good deed, a +x is added to the LHS. Now, during the process of doing the good deed, he goes through pain (ex. - Sitting up all night and helping someone do his homework is a good deed. But when you do it, you miss your sleep (pain)). The magnitive of this pain is exactly equal to the magnitude of the good deed. Therefore |pain| = |good_deed|. Let the magnitude of both of them be equal to 'x'.

If we write it in equation form, we get

x = -x + expected_reward

Here the x on the LHS is the good deed. The -x on the RHS is due to the pain felt while doing the good deed. The only way to balance the equation would be if a positive term were added on the RHS of the equation. Clearly, this would be the expected reward after having done the good deed and having endured the pain of doing the good deed. We can clearly see that expected_reward = 2x. Hence Proved :)

Clearly, the most critical assumption here is that we always get out of life exactly what we put into it. Do you believe that???

Abhiram.

History of Sorting Algorithms

2009-07-18T23:03:00.017+05:30

The story behind an invention/discovery is always fascinating. Be it Newton having an apple fall on his head, or serendipitous happenings which led to discoveries like Penicillin, Radioactivity, etc - there is always something intriguing about stories of such a kind. Often, many inventions/discoveries either do not have such a story or they have a story and it is not well known.

In this post, I would like to share with you the history of how various sorting algorithms were developed.
(1) Selection Sort - Invented by Mr. Selection
(2) Bubble Sort - Invented by Mr. Bubble
(3) Merge Sort - Invented by Mr. Merge
(4) Counting Sort - Invented by Mr. Count

Story of Selection Sort:-
Mr. Selection's mother was an English teacher. Once every 3 months, she bought home examination papers to evaluate. Once the valuation was complete, she liked the papers arranged highest marks first and lowest last. She had a practice to praise the highest while handing out the paper, and at the same time, rebuke the person who scored the least. Having the highest scorer's sheet handed out first ensured that everyone got to know who he/she was; it would be correct kind of boost required for the student. Also, having the person who scored least to be called out last would help because by then, everyone else would have got their papers and would be busy with their own sheets, so least attention is drawn to it.

His mother gave him the task of arranging the papers. He decided to follow this strategy to arrange the papers.
(1) Place all the sheets side-by-side.
(2) Scan from left to right and find out the guy who got the highest.
(3) Take his sheet and place it face-down on another table.
(4) Among the leftover papers, scan again from left to right and find out the highest in the remaining set.
(5) Place his paper too, face-down, on the paper already placed on the table.
Repeat (4) and (5) until the entire set is complete.

10 years later, when he had to write a program to sort values, he recalled arranging the papers. He realised that in every pass, he selected the maximum and then placed it aside. He did the same thing in the program and named the algorithm after himself :)
Story of Bubble Sort:-
Mr. Bubble was a student of Pineapple High School Convent. During the daily prayers, all students of the same class stood together in a line and it was required that the students stood in ascending order of their heights. During the first ever time the students had to make a line, there was utter chaos. Everyone was shouting... "hey you are shorter than me, come and stand in front of me", "hey lambu, go and stand behind re", etc... The teacher called for silence!!! She thought of a way to arrange all of them.

The first sorting process that struck her was to find the shortest one and place him first; find the next shortest one and place him second and so on... She realised that the process of finding the shortest student among a set of students was very tricky. When she scanned from the top to the bottom of the line often she would not be able to decide whether a guy near the end was shorter than a guy she saw in the beginning. She could only decide who was shorter if they stood beside each other. So she went to the head of the line. She started swapping two adjacent students if they were not in order. She realised that after the first pass, clearly the tallest guy was at the end. She then decided to do the same to the remaining set. She kept performing the same and soon the line was sorted.

Mr. Bubble was impressed with what his teacher did. This incident was etched in his mind. Years later, he read a paper authored by Mr. Selection about a sorting algorithm called selection sort. He somehow happened to recall his teacher's method of sorting and realised it was different from the selection sort. He realised how the teacher bubbled the elements to the ends of the array. He decided to try programming it. He programmed it and it worked. This was how the Bubble Sort was born!!!

Story of Merge Sort:-
Mr. Merge was a scientist working in basketball research laboratories. The lab was far away from his home and so he chose to rent a place closeby. While shifting, he packed all his books into small cartons. He was an avid reader, because of which there were a really high number of cartons.

Once he reached, he wanted to take out the books and arrange them on his shelf in order of their heights. He realised that opening all the cartons and then sorting the books would make too much of a mess. He decided that he would break his problem into smaller bits. He first opened the cartons and arranged the books in the carton according to height. This was not much of a problem because the cartons could not hold too many books. Once arranged, he merged the cartons. He realised that having already sorted them made his job a bit easier. Merging small sorted sets of elements to get one full big sorted set was easier than sorting the entire large set together!!! The next thing you know - Merge Sort was born!!!

Story of Counting Sort:-
Mr. Count's little brother studied at samsung kindergarten school. Count would go to pick his brother up every afternoon. One afternoon, he was a bit early, and he could overhear what was going on in his brother's class. The teacher had listed a huge array of alphabets (randomnly and with repetition). Each kid was asked to sort the list. The teacher believed that this exercise would help kids get familiar with the alphabets as well as develop their memory (for a human to sort a list, it does require a little bit of memory usage on his part). Mr. Count's little brother could not do the exercise. The bell rung and before the teacher dismissed the class, he told Count's brother - "I will not send you home tomorrow if you do not complete this exercise in front of me".

Mr. Count then started wondering how he could make his little brother's job easy. The real problem for the kid was that there were too many alphabets on the board. The kid indeed knew the order of the alphabets when he was asked to chant it - "abcdefghijklmnop...". But to re-arrange them when they were in random fashion was a little difficult for the kid. Everytime, he had to recite the alphabet in his head. This was taking a lot of time.

Mr. Count then came up with a strategy:-
(1) He asked his brother to make a table with two colums and 26 rows
(2) In the first column, write down numbers alphabets from a to z
(3) Now, start scanning the array left-right and as you encounter each alphabet, put a line against the corresponding letter in the table. Once done, forget about the array.
(4) Now just scan the table from top to bottom. The number of times each letter had to be listed was obviously determined by the number of dashes for that particular alphabet.
(5) Hence, a top to bottom scan; with simultaneous listing of the alphabet would give the sorted list the teacher wanted.

Count's brother caught on with this idea and could complete the exercise next day with significant ease. The brother excitedly mentioned to count that the teacher was particularly impressed about the speed with which he completed the task.

When count was a university student, he had to write a program to sort a similar kind of list. The range of values was limited and known. There were no memory constraints and the process of sorting had to be as fast as possible. It goes withough saying that this was the birth of the counting sort.

Things to notice:-
(1) Mr. Merge had the same problem of sorting a large number of items and that too as efficiently as possible. A Merge sort is indeed used in that kind of a situation.
(2) Mr. Count had a "limited range of values". That is indeed the kind of situation a counting sort is used in!
(3) Both Mr. Selection and Mr. Bubble did not have too many things to handle at the same time. Selection and Bubble Sort are used for small arrays!

It goes without saying that these stories are pure crap. They are just things I made up to satisfy myself. However, I somehow feel the real stories could not have been much different; maybe different situations and also the scientists' parents being a little more creative in naming their children :P.

This is not an attempt from me to trivialise any matter. I have a feeling that making up stories like this for everything new you learn aids your understanding. I try and do it for everything I learn and I find that it really helps me.

Another thing I would like to point out to people. Successful computer scientists are not people who sit in front of the computer all day. They are people who observe everything around them and find inspiration to translate human language into a language the computer can understand. Edsger Dijkstra once said "...computer science is no more about computers than astronomy is about telescopes...". Often I hear dialogues like "...I don't want to get into computer science because I hate sitting in front of the computer all day man...". I hope this post shows those people that computer science does not need you to stare at the screen all the time; studying computer science does not mean you will spend a life building meticulous GUIs for Grocery Applications at Infosys! There is a difference between the terms Information Technology and Computer Science. Please do not use them interchangeably!!! Computer Science is as evergreen a science as any other. Booms and busts in IT have no effect on the science and its sacredness. This realization does not dawn easily on computer engineers even, let alone the others. I just wish that people did not have this misconception.

Abhiram.

The Good in Bad

2009-02-16T17:24:00.021+05:30

I have always enjoyed reading the Mahabharata and Ramayana and consider them to be the greatest works ever. According to me, every incident in them has more than just one surface meaning and teaches a lot of lessons to the one who delves deep. Very recently my father was propounding his ideas on the Shabari story. He called the story distasteful and an insult to Lord Rama. He has always believed that the epics are great literary works by genius minds but he finds the idea of them actually having happened to be ridiculous.

His views on Shabari left me wondering... Why would a distasteful story be woven into an otherwise grand literary piece? Why would Valmiki want to portray an incident which did not have a good moral behind it? I told myself - there was no way this incident did not have a strong moral lesson behind it. Though I initially could not tell what, I was sure that there were hidden messages.

Often, when you tell yourself there is good, and you try hard to see good in something that looks bad otherwise, you end up finding it. My counter-argument to my father's theory is that the incident is not distasteful and that it teaches us three things:-

(1) It tells us how far we are from Lord Rama as human beings. If we were offered half-eaten fruits, we would either admonish the offerer or excuse ourselves from eating them (my favourite excuse is "loose motions" when I don't want to eat something). The Lord did not do that; he could see the devotion of the lady and he ate the fruits without complaints. At a higher level it means - when we come across something unsavoury, we must stop to think as to what could have caused it. The effect may be unpleasant, but the cause need not be so.

(2) It tells us how far we are from Shabari as human beings. If we had prior notice that Lord Rama would visit our home, we would try to clean the place as much as we could and we would purchase those ridiculously costly Australian Apples (Rs. 30/- per piece and sometimes even more) or Alphonso Mangoes from Food World (dunno cost because I have never purchased them). We would wear the best clothes we have and try and put up a home which does not look like what it normally does. Shabari did not; her devotion was pure. Unlike us, she thought costly apples/mangoes would not impress the Lord. At a higher lever it means - the best way to impress the best it to be true. For example, the best way to answer tricky questions in an interview is to talk from the heart and not try to put up an image that is not what you are. Abstract generalities and infinitives are no good. To impress the best, be simple.

(3) Thirdly, I think there is a general moral. If you look at it from outside, offering someone half-eaten fruits is not wise. Shabari was blinded by her devotion and I think this incident tells us that too much of something, even if the "something" is good by itself, could finally look bad. Devotion is undoubtedly good, but too much of it in Shabari manifested in an act which an outsider would definitely brand as crazy. I don't think the moral directly takes a stand as to whether too much devotion is good or bad. It is just that you need a Lord Rama to appreciate you when you reach such high levels. As an example, it could happen that you read too much and write extremely complicated fundae in an exam that could cause your evaluator to not understand you. Reading a lot is good, but too much could result in disaster. I dunno if that is good or not!!!

I am posting this because I am not sure my analysis is complete and there is a chance that my analysis is wrong too. I gladly invite comments.

Jana Gana Mana - A R Rahman

2008-05-20T19:02:00.037+05:30

I have reposted this here.

Jana Gana Mana - A R Rahman

2008-05-20T08:28:00.000+05:30

[EDITED VERSION OF AN EARLIER POST]

‘Jana Gana Mana’, authored by the Nobel laureate Rabindranath Tagore in Bengali, was instituted as the national anthem of India in 1950. It is as sacred as the National Flag, but then while the flag has just one form and one appeal – the patriotic - and it is indeed treason to mutilate it, the anthem comes in varied renderings, and as many types of appeal. Together with Bharatbala, A R Rahman has produced a masterpiece. In this post, I wish to share parts of the artifact with the sole intention of spreading my own enjoyment. The patriotic is one such appeal, the principal one, at that.

Although it is said in jest that Indians are most prone to exhibit the highest patriotic sentiments when watching cricket matches, there is no gainsaying that the national anthem stirs some intense patriotic feelings deep within, pulls a string or two in the heart, as it were. I often wonder what should the tunes – the original set by Tagore himself, or its allotropic forms - have been made of, that they should be so potent! What is there in them that they manage to move me every time I hear it? Take this very version, for instance. Was the tune composed with that very intention of moving the listener? It couldn’t have been a mere coincidence, could it? If yes, isn’t it damnably UNBELIEVABLE! I run out of words when I attempt to express the beauty of the tune. I abandon the attempt...

A R Rahman's version is an effort to showcase the flavours of the national anthem through soulful music. This was a project in which over 35 great, accomplished musicians of the nation came together to sing or play the national anthem. Their rendering turned out to be a fantastic classic. Most of us would have probably watched this video at some point. The album I am talking about contains, in addition to several other things, this very video. One can get more information about this project here.

The album contains individual renditions of the national anthem by each of 35 artists, both instrumental and vocal. The culminating artifact, i.e. the video, was actually produced by choosing a specific artist's rendition of a specific line and then putting them all together. It would be churlish to expect yourself to stand stiff in attention throughout the video. In fact, I enjoyed the work with my eyes closed and my legs on top of my table. Although seemingly blasphemous, I assuaged my conscience by viewing Rahman's work as an outpouring of love for the nation (patriotism is a form of passion after all isn't it...) or, a poetic expression of love to a beloved nation, or a devotional chant to a sacred diety, or may be, just as musical meditation.

To me, love is respect in its highest form. Our respect for the national anthem need not be fearful, it can be thoroughly innate (we all took Shah Rukh Khan's side in Mohabbatein didn't we!). I found that sitting down while listening not only seemed appropriate but perhaps even necessary, to deal with the emotions that rush through you ... like when The Late Bhimsen Joshi employs micro-cadences or like when Pt. Jasraj sings gahe tava jaya gatha... or like when Rahman himself launches a clarion call: Jaya he, Jaya he, Jaya he... Every performer leaves behind a stamp on this most public of properties. Each one of us has a unique equation with our nation, and this fascinatingly unique album is a reminder of that.

Below, you shall find that I have uploaded the audio tracks in the album. Essentially, I have uploaded the audio versions of every artist's rendition. Please download them and enjoy. My decision to upload tracks was purely because I know that ending with a "please buy this album at your nearest store" would be completely pointless. By doing this, I believe a lot more people will experience the beauty of the creation. Technically, I am doing wrong! However, the fact that this will only lead to good feelings assuages my conscience. If ever I am tried in the court of Hades, I hope to be let off because this act of mine, I am sure, will eventually do more good than bad. Let me close by wondering what exhilarating feelings any human may get by his/her own national anthem!

[No Copyright Infringement Intended!]

[Although all renditions are fabulous, the ones I strongly recommend are coloured red]

Collective Renditions:-
1. Instrumental Version
2. Vocal Version
Individual Renditions:-
1. Pt. Hariprasad Chaurasia
2. Pt. Bhimsen Joshi
3. Pt. Vishwa Mohan Bhatt with Vikku Vinayakram
4. D.K. Pattamal with Nityashree
5. Ustad Amjad Ali Khan, Amaan Ali Bangash, Ayaan Ali Bangash with Vikku Vinayakram
6. Pt. Jasraj
7. Lata Mangeshkar
8. Ustad Sultan Khan with Vikku Vinayakram
9. S P Balasubramanyam
10. Pt. Shiv Kumar Sharma and Rahul Sharma
11. Dr. Balamuralikrishna
12. Shobha Gurtu - Alaap, Rendition
13. Ravikiran with Vikku Vinayakram
14. Ustad Ghulam Mustafa Khan with Ghulam Murtaza Khan and Ghulam Qadir Khan
15. Bhupen Hazarika - Alaap, Rendition
16. Saddiq Khan Langa - Alaap
17. Pt. Kartick Kumar and Niladri Kumar
18. Sudha Raghunathan and P. Unnikrishnan
19. Jagjit Singh
20. Rashid Khan - Alaap, Rendition
21. Asha Bhosle
22. Kumaresh & Ganesh with E. Gayathri
23. Begum Parweena Sultana - Alaap, Rendition
24. Pt. Ajoy Chakrabarthy
25. Pt. Ajoy Chakrabarthy with Kaushiki Chakrabarthy
26. Hariharan - Alaap, Rendition
27. Kavita Krishnamurthy with Shruti Sadolikar
28. Rabindranath Tagore - ORIGINAL RENDITION

I am the Greatest!!!

2008-04-22T14:45:00.013+05:30

No No No...! This is not an exclamation from me. "...I am the greatest! I am the greatest thing that ever lived..." was Muhammad Ali's proclamation. He said that quite a few times during his extremely illustrious career. Most people are of the opinion that the exclamation was unbecoming of the champion that he was. I, however, respect him only due to his guts to say I am the greatest loudly and confidently in public.

Most great sportsmen, Pele, Maradona, Bradman, etc have said something on those lines. Napolean, Alexander, etc too have gone the Muhammad Ali way. History is replete with such acts - acts which have been called vain, egoistic, over-confident, or even conceited. The commoner would never ever think of proclaiming such a thing in public. He would say "...I would never ever have said thus..." or "...what a thing to say in public...". Perhaps he is of the view that saying something like this, is indicative of lack of modesty, and modesty is always a desirable trait of course. I would say it is his mediocrity that is preventing him from proclaiming such a thing, and not his modesty.

I salute the people who have guts to say I am the greatest in public. Disregarding the apparent lack of morality in these deeds and statements, I think one ought to perceive in them the seeds of supreme self-confidence; a confidence not born out of arrogance, but out of having achieved something truly remarkable. Muhammad Ali had blazed a trail in the annals of boxing. Pele used to score goals for fun. Bradman has an average that I haven't managed to achieve even on computer simulations of Test Cricket.

"...calling yourself the greatest is being egoistic..." or "...by saying you are the greatest, all you are doing is getting attention for yourself, without having done anything... One would rather act than talk..." - I find these ideas pessimistic and even defeatist. These remarks are from those who tend to look at the bleaker side of life all the time. Deep down, all of us think we are the greatest. Then what is it that prevents us from proclaiming it? It is fear - fear of competition, fear of being proven wrong. One thinks what if someone proves that he is greater than me after I say I am the greatest.... I will lose face then...

People feel that diffidence, of a kind that I call pessimism, is a sign of modesty (which is a desirable trait). I think it is mediocrity in the garb of modesty. At the same time, confidently proclaiming such a thing in public is indicative of the absence of fear of competition and of being proven wrong. And that is always an off-spring of supreme prowess, which comes from the pure hard work. It requires mental tenacity to show your left cheek when someone slaps the right one. However, to proclaim such a dictum requires even greater tenacity, possibly the divine power of a Jesus Christ. That is guts - the guts to pontificate.

Let us go to our lore: There was this Arjuna’s lament that he would not kill his uncles and cousins; he had his fear of wrong, his perception of righteousness, his view of duty and his sense of piety. But then, what did it all prompt from the Bhagwan? It was perhaps the greatest piece of literature. All out against a rather obdurate Arjuna, Lord Krishna says: “Look, Arjuna, I am the greatest. What I say is divine ordainment! You are not the judge of what is right or wrong; neither of what constitutes your duty. Fight I say; and fight, you will, for, mine is THE WORD OF GOD”. Similarly the very first and the most powerful of the Ten Commandments says: “I am the Lord, thy God: thou shalt have no other gods before me.”

Let us ask, what if Lord Krishna had said: “See, Arjuna, you should fight these fellows, if you ask me. Anyway, it is left to you”? It would have been a ‘modest’ Krishna alright, but an outright ineffectual one, at that. Then I do not see any reason why Muhammad Ali's proclamation is to be deemed as arrogance. After all, there are no second thoughts about who is the greatest boxer ever. If Ali had never exclaimed thus, he would have been confined to the dustbins of history as a run-of-the-mill champ.

Brash acts, deeds and statements are not always to be despised. They should not be uniformly branded as the outcome of immaturity or immodesty. In fact they should not be the subject of a value-judgment at all. They do not always depict pride or uppishness. More often that not, they could be innate faith in oneself, finding utterance. Surrounding them there could be the fragrance of immense success; and may be, behind them a touch of divinity itself!

I hope a day arrives when I can confidently tell the world I AM THE GREATEST! At the moment, neither am I close to the greatest, nor do I have to the guts to say it. However if that day arrives, I envisage a similar post on someone else's blog with the pic below

Code Time

2008-04-14T23:05:00.022+05:30

This post contains some programs that I have personally written to solve elementary problems. I am sharing these just so that people can see different ways of solving the same problem. Also, I claim that the methods used are very simple and natural.

Disclaimer:-
Please don't send me comments/scraps/mails giving me links where you have found the same logic. Its just that I have thought about these solutions without aid from any external source(internet, book or someone else). It may exactly/partially mimic what you have seen somewhere else or what you have thought of yourself. If that is the case, then just skip reading this post.

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

Q. Given a string, print all the unique permutations of the string in lexicographic order.

Ans. The methods that I have detailed below is special in that it prints "unique permutations".

Algorithm:-
1. Maintain an integer array which stores the number of occurrences of each character in the input string( hash the input string). It should be such that arr[character] gives the number of occurrences of character in the input string.
2. Allot the first character which has at least one occurrence. Then recursively permute the other part.
3. In the next iteration, make sure you choose a different character to allot. Even if the previous character you allotted occurred more than once in the input string, do not allot this once again (this is the key to ensure you get only unique permutations).

Steps 1 and 3 are the crucial steps. Step 1 makes sure that the permutations are in lexicographic order and Step 2 makes sure that only unique permutations are generated. Download the code from here.

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

Q. Given a sentence reverse the order of words in it. For example-
Input - who is the person over there
Output - there over person the is who

Ans. This is an all-time favourite question for On-Spot-Programming question paper setters. There are quite a few things you can do to solve this problem.
1. From the end of the string, come back to find a space. From there, go forwards printing all the characters till the occurrence of the next space. Do that until you reach the beginning of the string.
2. Put a \0 in wherever there is a space and do a printf("%s ",ptr) every time you find a a \0.
3. Take input as a sequence of words. Print the words in reverse order.
4. Reverse the string. Later on, reverse each word in it.

All the above methods are simple and equally efficient. Though this is an oft repeated question, often I find people struggling with this, purely because of silly mistakes. I thought of a way that is safe and easy to reproduce too. I do it recursively and that is what is special here.

Steps:-
1. Form the first word. If the breaking character is a space, then do a recursive call.
2. Keep doing step 1 until you get a newline character. Now start printing the words.

Download the code here.

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

Q. Write a program to simulate a simple Snake as seen in mobiles.

Ans. I have coded this particular program on Turbo C . It is easily reproducible on other compilers only if you know the corresponding functions.

What is special this time??? - I have not used the graphics library at all.

Download the code here. If you have any issues executing it, please let me know.

Chants of India - My Review

2008-03-27T21:18:00.029+05:30

I stumbled on this album accidentally. It was the track Hari Om that first caught my fascination. Normally, I do not like improvizations (remixes) of original tracks, like Anuradha Paudwal's Gayatri Mantra, but Chants of India is an exception.

Chants of India is Pt. Ravi Shankar's effort to set Sanskrit chants from ancient Hindu scriptures to music. As expected, the result is a captivating mix of chant and music. This collection of mantras and prayers from the Vedas, Upanishads, and other scriptures powerfully transports the listener to a place of peace where it's possible to be one with the universe. I always thought phrases like "I feel one with God when I hear music" was just impressive writing and never actually true. This collection shattered that opinion of mine. It starts, as in traditional Indian music, with a chant for Lord Ganesh. The collection is quite varied from chantings of a specific God such as the goddess of Learning (Saraswati); chantings from the Gita, the vedas; to the famous Gayathri mantra,. The chants are authentic in their rendering in terms of the utterances and adherence to tradition.

It's as if a heavy, enveloping cloak of serenity falls from the dark. A number of instruments are employed to accent the mighty "OM" thread that weaves itself through the cloth of this album, bringing together deep, ominous voices with delicate, earthly instruments.

Track Listing (Download)
1. Vandanaa Trayee
2. Omkaaraaya Namaha
3. Vedic Chanting (One)
4. Asato Maa
5. Sahana Vavatu
6. Poornamadah
7. Gaayatri
8. Mahaa Mrityunjaya (Triyambakam Yajamahe)
9. Veena Murali
10. Geetha (Karmanya Vadhikaraste)
11. Mangalam (Tala Mantra)
12. Hari Om
13. Svara Mantra
14. Vedic Chanting (Two)
15. Prabhujee (File split into three parts - part1, part2, part3. Download all of them and open the zip file. Extract the track from there)
16. Sarve Shaam

Go here for the text. Peace be with you :)

SOME PARTS OF THE POST HAVE BEEN FLICKED FROM ELSEWHERE!

Solutions - Part II

2008-03-25T14:15:00.012+05:30

Hello Everyone,
I am back. I shall continue posting a few more questions. I would like to point out that most of these questions have not been made up by me; they have been flicked from wonderful sources :)

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

Q. Why is the size of an empty class not zero?

Ans. This is basically to ensure that the addresses of two difference objects will be different. Go here to read more about this.

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

Q. Rama has n cigarettes. He smokes them one by one keeping the butts as he smokes. Once he has k butts, he can roll over a new cigarette. Given n and k, how many cigarettes can he smoke?

Ans. For example if n = 29 and k = 8, then lets says peter can smoke x cigarettes. x=29+(extra). Now peter has 29 butts. He needs 8 butts for a cigarette. So he can smoke 3 cigarettes more(29/8); x=32. He used 24 butts for 3 cigarettes. So he has 5 butts left out. Also, the 3 cigarettes that he smoked(extra). So he has 8 butts and thus he smokes one more. So x=33. Now he has one butt left out and he cannot do anything with that. So basically he smokes 33 cigarettes.

One could easily write an iterative algorithm. But here I shall show a really nice way of solving this problem. The recurrence relation is pretty straightforward and simple.
N = n + f(n,k)
f(n,k) = n/k + f(n%k + n/k , k)

If expanded, f(n,k)
= n/k + ((n/k)+(n%k))/k + (((n/k)+(n%k))/k+((n/k)+(n%k))%k)/k + ...
= n/k + n/k^2 + (n%k)/k + n/k^3 + (n%k)/k^2 + ...

We know that (n%k)/k is 0 because a/b here refers to the floor value of a/b. So we have...
f(n,k) = n/k + n/k^2 + n/k^3 + n/k^4 + ...

Therefore f(n) = Sigma n/(k^t) where t = {t | k^t <= n} f(n,k) = n/k*(1/k^t - 1)/(1/k - 1) = n/k*((1-k^t)/k^t)/((1-k)/k) = n * (k^t -1) / (k^t * (k-1)) Now k^t is less than or equal to n. Therefore f(n,k) = (n-n/k^t)/(k-1) Since k^t is less than or equal to n, n/k^t =1. Therefore f(n,k) = (n-1)/(k-1) . Let me illustrate the formula with the above example itself. n = 29 and k = 8. Answer = n + (n-1)/(k-1) = 29 + (29-1)/(8-1) = 33. --------------------------------------------------------------------------------------------------

Q. Given a number n, find the nth number f(n) whose cube ends in 888. (192 is the first number whose cube ends in 888). f(n) must be found in O(1).

Ans. It is said that the cube ends in 888. Without any loss of generality:- n^3 = 1000y + 888 (Note that 1000y + 888 is a number whose cube ends in 888) We know if the cube of a number ends in 888, then the number ends in 2. Therefore, (10x+2)^3 = 1000y + 888 (Now we need to find x and append a 2 at the end)
8(5x+1)^3 = 1000y + 888
(125x^3 + 75x^2 + 15x + 1) = 125y + 111 (dividing above equation by 8)
125x^3 + 75x^2 + 15x = 125y + 110
125x^3 + 75x^2 + 15x = 125y + 125 - 15
75x^2 + 15x + 15 = 125y + 125 - 125x^3
75x^2 + 15x + 15 = 125(y+1-x^3)
75x^2 + 15x + 15 = 125k (A multiple of 125)
15(5x^2 + x + 1) = 125k
3(5x^2 + x + 1) = 25k
3 * something is a multiple of 25, therefore clearly, something = multiple of 25
5x^2 + x + 1 = 25k

Let x=25t+r (r is between 0 and 24)

Substituting for x, we will get
5r^2 + r + 1 = 25k
So we need to find r between 0 and 24, which when substituted in 5r^2 + r + 1, would yield a multiple of 25. By trial, we get r as 19.

Therefore x = 25t + 19

The final algo would look like:-
INPUT n
x = 25(n-1) + 19
x = (x*10) + 2 //append a 2 at the end
OUTPUT x

Solutions - Part I

2008-02-10T20:38:00.040+05:30

CODEFINGER was the On-Spot-Programming event and Casino RoYahoo! was the Yahoo Internship event. Both consisted of two rounds - a preliminary written round followed by the final round which required the finalists to program directly on a system provided to them.

Here I shall post the solutions to only a few questions. One can download the question papers here. Feel free to contact me for the answers to the other questions

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

Q. What is the output?

int main()
{
..... i=3;
.....( "%d\n", sizeof(i==3? 5 : 6.8) );
.....return 0;
}

Ans. sizeof is a unary operator which returns the number of bytes its operand occupies. It is a compile-time operator because at run-time, type identification cannot be done in C. Since it is compile-time, it is to be noted that the expression is not evaluated (It is for the same reason that i=5 ; sizeof(++i) ; print i would output 5 itself, i.e. the ++i is not executed). Thus first of all, int i=3 is inconsequential.
The result of the expression i==3? 5 : 6.8 should be large enough to hold either an integer or a double(default for real values). Thus the output of the above code snippet is 8.

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

Q. Why can we have Virtual Destructors but not Virtual Constructors?

Ans. Virtual mechanism acts on complete objects. If something is virtual, it means it can be over-ridden by a sub-class. When a constructor is in the process of execution, the object is not complete. Thus it makes no sense to have virtual constructors.
But we can have virtual destructors because the fact that a destructor is being executed means the object has been constructed completely.

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

Q. The following function void insert_right(int value , int element) aims at inserting value to the right of element in a linked list whose header node is first. The structure definition of the linked list is as follows:-
struct node {int info; struct node *next};
The following code gives a run-time error for certain cases. Point out the cases and make the correction so that it gives correct output for all cases.
void insert_right( int value, int element )
{
.....struct node* cur=first, *temp;
.....while( cur->info != element && cur != NULL)
..........cur = cur->next;
.....if(cur==NULL)
..........printf( “Element not found.\n” );
.....else
.....{
..........temp = get_new_node(); //returns a pointer to struct node
..........temp->info = value;
..........temp->next = cur->next; cur->next = temp;
.....}
.....return;
}

Ans. The correction is cur->info != element && cur != NULL must be changed to cur != NULL && cur->info != element. The reason is easy to make out. When the value that is being searched for is not present in the list, we reach the end of the list. At that point cur = NULL. So cur->info results in access violation, resulting in the run-time error.

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

Q. Write a one-liner to find the value of n mod 2^s without using the % operator. No looping allowed either.

Ans. The value of n mod 10 is always the last digit of the number. This can be proved pretty easily-> if we have a number abcd where a,b,c,d are the individual digits, it can be expressed as abc*10 + d. Thus it is obvious that the remainder when divided by 10 would be the last digit itself. Similarly the value of the remainder when a decimal number is divided by 100 are the last two digits of the number.
We can extend this logic to powers of 2 as well. The value of a number mod 2 is the last bit in the binary representation of the number. Similarly the value of a number mod 4 is the last two bits in the binary representation of the number.
Illustration:-
If we have a number 10100100101, the number mod 16 is basically the last four bits of the number,i.e. 101 which is 5. The reason for this is pretty simple. The above number can be actually expressed as (1010010)*16 + (0101). Thus is it clear that the remainder is 0101.

Hence to find the remainder of a number divided by 2^s, all we have to do is mask all but the first s bits from the right side. Therefore the remainder is given
by the expression rem = n[bitwise and]((1[shift left]s)-1).

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

Q. The expression i = (i + 1)%10 generates values like this:
...1->2->3->4->5->6->7->8->9->0->1->2->3->4->5->6->7->8->9->0->1...
Write an expression which will generate values like this:
...8->7->6->5->4->3->2->1->10->9->8->7->6->5->4->3->2->1->10->9->8...

Ans. I am not sure whether the question statement is very clear. Basically if I begin with say i=5 and successively perform i=(i+1)%10, then the sequence of values generated are 6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,.... Basically, i gets incremented till 9 and then comes back to 0. Now I want a statement that would generate values in the order 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10...

First of all, let us see how one can generate the sequence 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 9...(A)
At first thought, i=(i-1)%10 is what comes to mind. This works for all instances other than i=0. When i=0, the next value should be 9. So we need to handle the case where (i-1) goes negative. Now we know (a+b)%b = a%b. Therefore (i-1)%10 = (i-1+10)%10. i=(i+9)%10 thus generates a sequence (A). The expression can also be though of in this way going back one circularly is equivalent to going ahead 9 circularly.

Now the sequence asked for is 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 9, 8...(B) This sequence is just sequence (A)+1. Thus the first idea here is that i=(i+9)%10 can itself be used. Now, the value of i in sequence (B) is the value of i in sequence (A)+1. Therefore we have:-
ia=(ia+9)%10
We want the expression for ib where ib is ia-1
So, ib-1=(ib-1+9)%10
ib-1=(ib+8)%10
ib=(ib+8)%10+1
Thus the expression i=(i+8)%10+1 will generate sequence (B). Pardon me for the unclear explanation. But this is the best I could do.

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

Q. Change one character in the following code to get the output as 20 x's.
int i,n=20;
for(i=0; i [less_than] n; --i)
....printf("x);

Ans. The above question is a well known question. The answer is
int i,n=20;
for(i=0; i [less_than] n; --n)
....printf("x);

(or)

int i,n=20;
for(i=0; i + n; --i)
....printf("x);
Now, this question was asked just for the heck of it. Coming up next is a bouncer. Try it!!!

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

Q. Add one character to the following code to get the output as 21 x's.
int i,n=20;
for(i=0 ; i [less_than] n ; --i)
....printf("x");

Ans. I happen to recall that only one team got this one right. The answer to it is...

int i,n=20;
for(i=0 ; ~i [less_than] n; --i)
....printf("x")

You are supposed to think like this. For the previous question, if we had the for condition as -i[less_than]n, then the output would have been 20 x's. If the condition had been -i[less_than](n+1), then the output would have been 21 x's. Similarly if the condition was (-i-1)[less_than]n, the output would have been 21 x's. -i is 2's complement of i. -i-1 would be i's 1 complement. Thus, the solution is ~i[less_than]n.

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

There is more coming up...
Abhiram Natarajan

INFINITY '007

2008-02-10T19:59:00.009+05:30

Hello everyone! It has been long time no blog for me. Currently, I am interning at Cisco. The place is nice but the work.... NO COMMENTS.

INFINITY '007, the annual(supposed to be) departmental fest of the Dept. of Information Science of R V College of Engineering was a huge huge success. It had everything a fest should ideally have - great events, great organizers, great prizes, great crowd and ME! It was a truly marvelous experience to be part of it.

I was in-charge of two events - On-Spot-Programming and the Yahoo Internship challenge. It was both challenging and fun setting questions for these events. Here I shall post the question papers and the solutions(I know) for the questions. Please note that suggestions, comments, questions, criticism, etc. are welcome. You can contact me personally or even comment here itself.

Signing off...
Abhiram Natarajan.

An Interesting Problem

2007-07-13T21:54:00.004+05:30

The Problem

There is man named "mabu" for switching on-off light in our University. He switches on-off the lights in a corridor. Every bulb has its own toggle switch. That is, if it is pressed then the bulb turns on. Another press will turn it off. To save power consumption (or may be he is mad or something else) he does a peculiar thing. If in a corridor there is `n' bulbs, he walks along the corridor back and forth `n' times and in i'th walk he toggles only the switches whose serial is divisable by i. He does not press any switch when coming back to his initial position. A i'th walk is defined as going down the corridor (while doing the peculiar thing) and coming back again. Now you have to determine what is the final condition of the last bulb. Is it on or off?

The Input

The input will be an integer iandicating the n'th bulb in a corridor. Which is less then or equals 2^32-1. A zero indicates the end of input. You should not process this input. The Output Output "yes" if the light is on otherwise "no" , in a single line.

Sample Input

3
6241
8191
0

Sample Output

no
yes
no

I came across this problem during a programming contest. Although the lengthy problem statement can confuse, it is really straightforward. You are given number n. All you have to do is check whether n has an even number of divisors or odd. If even, you print "no" otherwise you print "yes".

A Naive Implementation:-
for i = [1,n]
…if n is divisible by i
……..count = count + 1
if count is even
…print no
else
…print yes

This was what struck me initially. However, I got a "Time Limit Exceeded" from the online compiler. Repeated efforts to optimize were all futile.

So it became clear, that I must design an algorithm markedly better than the naive one shown above. It took me a while ....

Well, what I finally did was this…. Check if n is a perfect square. If yes, the print “yes”, else print “no”. The proof follows.

Assume n is not a perfect square. We can see that when n is represented as a product of two numbers, one among m would be lesser than √n and the other would be greater than √n.

Consider the set of divisors of n. Let us say that there are x divisors of n below √n. Now, each of these x divisors would give an unique and different dividend when they divide n. We can see that the set of these dividends are indeed the set of divisors of n which are greater than √n. So this means that for every multiple pair, there is another multiple pair, which is just the reverse. Thus, we can say that the multiple-pairs themselves occur in pairs, which leads to the conclusion that the number of divisors for a non-perfect square number is even.

ILLUSTRATION

28 = 1 * 28
= 2 * 14
= 4 * 7
= 7 * 4
= 14 * 2
= 28 * 1

There are six multiple-pairs of 28. Among the six, three of them are unique and the other three are just mirror images.

Now, for a perfect square, the same argument would hold good. But there is the extra pair of √n * √n = n. This is the only other pair, so finally the number of divisors are odd.

So now our final algorithm would look like this.

if n is a perfect square
….print yes
else
….print no

Moral of the story:- Analogous to "Think before you ink", we have "think before you bang away on your keyboard"...

Broken Wings - Kahlil Gibran

2007-07-03T02:10:00.005+05:30

I had never really been moved by "romantic" movies or songs or poems. However, this book changed all that! Very unlike the other normal love stories, Broken Wings embraces the idea of unconditional love. It is redolent with images. Kahlil Gibran is truly a genius.

I would recommend this book to everyone. You can download it here. Small book, but trust me each line would hold your attention and make you think. I have seen quite a few people pride themselves saying "I do not like romantic mushy love stories. They are boring ...." Mostly Men... And some who consider love as a sign of weakness, and something unscientific. I was one of them!

Though I still do not seek out such stories/works, I enjoy them when I stumble upon them. This book, if read with an open mind, will cause even the coldest and shrewdest person to view love as a mystery. Try it. You will be defeated!!!

Factorials of Large Numbers

2007-06-26T22:41:00.017+05:30

4023872600770937735437024339230039857193748642107
146325437999104299385123986290205920442084869694
048004799886101971960586316668729948085589013238
2966994459099742450408707375991882362772718873251
9779505950995276120874975462497043601418278094646
49629105639388743788648733711918104582578364784997
7012476632889835955735432513185323958463075557409
11426241747434934755342864657661166779739666882029
1207379143853719588249808126867838374559731746136
08537953452422158659320192809087829730843139284
440328123155861103697680135730421616874760967587
134831202547858932076716913244842623613141250878
020800026168315102734182797770478463586817016436
502415369139828126481021309276124489635992870511
496497541990934222156683257208082133318611681155
36158365469840467089756029009505376164758477284
21889679646244945160765353408198901385442487984
95995331910172335555660213945039973628075013783
76153071277619268490343526252000158885351473316
117021039681759215109077880193931781141945452572
23865541461062892187960223838971476088506276862
96714667469756291123408243920816015378088989396
451826324367161676217916890977991190375403127462
22899880051954444142820121873617459926429565817
46628302955570299024324153181617210465832036786
90611726015878352075151628422554026517048330422
61439742869330616908979684825901254583271682264
58066526769958652682272807075781391858178889652
20816434834482599326604336766017699961283186078
83861502794659551311565520360939881806121385586
0030143569452722420634463179746059468257310379
0084024432438465657245014402821885252470935190
62092902313649327349756551395872055965422874977
40114133469627154228458623773875382304838656889
7646192738381490014076731044664025989949022222
1765904339901886018566526485061799702356193897
01786004081188972991831102117122984590164192106
88843871218556461249607987229085192968193723886
42614839657382291123125024186649353143970137428
53192664987533721894069428143411852015801412334
4828015051399694290153483077644569099073152433
2782882698646027898643211390835062170950025973
89863554277196742822248757586765752344220207573
6305694988250879689281627538488633969099598262
8095612145099487170124451646126037902930912088
9086942028510640182154399457156805941872748998
0942547421735824010636774045957417851608292301
353580818400969963725242305608559037006242712
4341690900415369010593398383577793941097002775
347200000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
00000000000000000000000000000000000000000
000000

That is the value of factorial 1000. Writing a program to print the factorial of a number is one of the most basic and almost elementary programming exercises. But naturally the simple one that we wrote in class is limited in that it cannot output the factorial of numbers beyond 20 (64 bit integers). Below is the description of a method that would generate the factorial of numbers far greater than 20. I believe the method is correct - I know for sure that the output is perfect for 1! to 5000!.

As one would know, fact(n) = 1 * 2 * 3 * ..... * (n-1) * n. To generate factorials of large numbers, the key is multiplication. If we knew how to multiply large numbers, the job is done. When I say large numbers, I mean numbers with 50 digits each or even more. To achieve this, let us just recall the basic multiplication procedure that we learnt in our 3rd grade.

NOTE:-There are few things to be noticed in any multiplication. The last digit of the answer is determined only by the last digits of the two numbers being multiplied. For example, 3*4 or 23*44 783687268732683*2313123124 would all end with 2. Similarly the last two digits of the answer are determined only by the last two digits of the two numbers being multiplied. 12*24 or 912*524 or 1231123211212*7272896782687687624 would all end with 88. So the basis of the entire logic lies in the fact that parts of the answer are affected only by parts of numbers being multiplied.

A careful look at the above figure should give us an idea. At a point of time, we are not multiplying more than two single digit numbers. Thus, with careful handling of the numbers, we can be sure that the holistic procedure shown in the diagram can be used to multiply two numbers, each having 1000 digits or even more. All we do is save our answer at every step and finally add all the intermediate answers to obtain the final answer. This is the standard multiplication procedure. The logic behind it is easy to understand.

4567 * 8767
= 4567*(7+10*6+100*7+1000*8) = 4567*7 + 10*(4567*6) + 100*(4567*7) + 1000*(4567*8)

Let T1 = 4567*7, T2 = 10*(4567*6), T3 = 100*(4567*7), T4 = 1000*(4567*8)
Referring to the figure above, we can say that the first number in the multiplication (31969) is actually value of T1, the second number (274020) is the value of term T2 and so on. We add all the values to obtain the final answer as 40038889.

Let us now generalize the multiplication procedure. Take two numbers abcd and efgh where a,b,c,d,e,f,g,h are the digits of the numbers.

m = abcd * efgh
m = abcd * (h + 10*g + 100*f + 1000*e)
= (d + c*10 + b*100 + a*1000) * (h + 10*g + 100*f + 1000*e)
= (d*h)+10*(d*g + c*h)+100*(b*h + c*g + d*f)+1000*(a*h + b*g + c*f + d*e)+ ... ---(1)

m = d1 +10*d2 +100*d3 +1000*d4 + ........ 10^(n-1)*dn ---(2)
where each of the d's <= 9

Our main idea is to write a program to do the multiplication. If we get equation (2), i.e. if we manage to obtain the values of d1, d2, ..... dn, then the final answer is the number formed by concatenating the digits d1...dn in reverse order, i.e., dn, dn-1 ..... d1. So our aim reduces to obtaining (2).

(1) is easily achievable. So all we have to do is transform (1) into (2). Though (1) and (2) look similar, there is a critical difference. For instance, d*h is not necessarily equal to d1. The numbers d1, d2, ... are all lesser than or equal to 9. d*h is not necessarily less than or equal to 9. Same is the case with d2 and (d*g + c*h).

The main problem lies in the fact that d*h, for example, might be a two-digit number. Let d*h = AB where A,B, are single digit numbers. Now, d*h = 10*A + B.
So (1) can be written as
m = B + 10*(d*g + c*h + A) + ......

"...This basically means that in the case where we get an intermediate answer as a number with two digits or more, we just take it as a carry...". I shall use this basic idea to obtain the value of 4567*8767 using (1)

Here a=4, b=5, c=6, d=7, e=8, f=7, g=6, h=7.

d*h=49. Take d1=9 and carry=4
c*h + d*g=42+42=84. Add carry to this. So value becomes 84+4 = 88. Take d2=8 and carry=8
b*h + c*g + d*f=35+36+49=120. Add carry to this. Value=128. Take d3=8 and carry=12
a*h + b*g + c*f + d*e=28+30+42+56=156. Add carry to this. Value=168. Take d4=8 and carry=16
a*g + b*f + c*e=24+35+48=107. Add carry to this. Value = 123. Take d5=3 and carry=12
a*f + b*e=28+40=68. Add carry to this. Value=80. Take d6=0 and carry=8
a*e=32. Add carry to this. Value = 40. Take d7=0 and carry=4
d8=carry=4

When we concatenate d8,d7,.....,d1, we get 40038889!!!!! Which is the answer we want.

Basically, I used (1) itself. The only point is that when I got a value with more than one digit, I just took the last digit of the value into the answer and took the remaining digits as the carry. I took care to add the carry to every intermediate value I obtained. To help writing a program easily, I would like to illustrate the above multiplication procedure in a better way.

a*0 + b*0 + c*0 + d*h=49. Take d1=9 and carry=4
a*0 + b*0 + c*h + d*g=42+42=84. Add carry to this. So value becomes 84+4 = 88. Take d2=8 and carry=8
a*0 + b*h + c*g + d*f=35+36+49=120. Add carry to this. Value=128. Take d3=8 and carry=12
a*h + b*g + c*f + d*e=28+30+42+56=156. Add carry to this. Value=168. Take d4=8 and carry=16
a*g + b*f + c*e + d*0=24+35+48=107. Add carry to this. Value = 123. Take d5=3 and carry=12
a*f + b*e + c*0 + d*0=28+40=68. Add carry to this. Value=80. Take d6=0 and carry=8
a*e + b*0 + c*0 + d*0=32. Add carry to this. Value = 40. Take d7=0 and carry=4
d8=carry=4

In case you did not spot it, all the terms contain a,b,c,d. the other digits follow this format:-
0,0,0,h
0,0,h,g
0,h,g,f
h,g,f,e
g,f,e,0
f,e,0,0
e,0,0,0

This is the method that has to be used to multiply two large numbers. Now coming back to generating the factorial, all we have to do is to repeatedly perform such multiplications and obtain the value of the factorial. Here I present the crux of the code. However, I suggest that you do not look at it. It would be best if you implement this logic on your own, cause it might very well turn out that your implementation is better than mine.

//fact(n)=n*fact(n-1)
/* The method of multiplication described above has been used to obtain the value of fact(n), i.e. fact(n-1)*n */
fact(1)=1; //initialization
INPUT:- An integer n
for i = [2,n]
.....str1 = i;
.....len1 = length(str1);
.....str2 = len1-1 number of 0s + fact(i-1) + len1-1 number of 0s;
.....len2 = length(str2);
.....carry=0;
.....for j = [0,len2-len1]
.........val=carry;
.........for k = [0,len1)
...............val = val + ( str2[j+k] * str1[k] );
.........END FOR
.........append val%10 to fact(i);
.........carry=val/10;
.....END FOR
.....append the digits of carry in reverse order to fact(i)
END FOR
OUTPUT:- The digits of fact in reverse order
NOTE:- str1,str2, fact are all strings.

Once again, I suggest that you implement this logic without looking at the above snippet. However, if you want the code, here it is.

A Cryptarithmetic Solver

2007-06-26T00:34:00.015+05:30

If you are reading this post, I assume you know what cryptarithmetic puzzles are, so I shall not belabor the point. In case you do not, please check this for a complete explanation. I also found some interesting papers on the topic. Check them out if you want to.

I have written a program in C which solves any cryptarithmetic equation (have tested it extensively on a lot of examples online). The input consists of three strings say S1, S2 and S3 and then a number (1 or 2 or 3 or 4), which denotes the operators + or - or * or / respectively. The programs generates all possible solutions for the crptarithmetic equation S1 (operator) S2 = S3.

LOGIC:-
There is nothing extra-ordinary in the logic. It is just a simple combinatorial technique, wherein I check all possibilities and output only the correct ones.
1. Take the unique characters.
2. Assign one possible set of values that you have not tried before. If no further assignments possible, exit.
3. Check it the assignment is correct.
4. If correct, the print the solution. Go to step 2.

crypt(letters,index)
{
......if all letters are assigned and the assignment is correct
...............print the solution;
...............return;
......for i = [0,10)
..........if i has not yet been assigned
................assign i to letters[index]
................crypt(letters,index+1); //recursive call
}

main()
{
........get the unique letters among the three strings
........call crypt(letters,0);
}

You can find plenty of places online which give you such puzzles. You can download the code from here. I have on purpose separated the entire program into many modules, more than what I would normally think was necessary. Minor optimizations are still possible, but I have refrained from doing them so as to not make the program look far too obfuscated. Please do report any errors that you find. Thank you.

Salutation of the Dawn

2007-06-26T00:32:00.008+05:30

This is a famous famous poem by Kalidasa. It tries to point out to us the importance of "today". Dale Carnegie refers to this poem in his book "How to stop worrying and start living". Clearly, if one follows exactly what is said in this poem, one would never experience "worry" (easier said than done of course).

Salutation of the Dawn

Listen to the Salutation of the Dawn!
Look to this day!
For it is life, the very life of life,
In its brief course
Lie all the verities and realities of your existence:
The bliss of growth
The glory of action
The splendor of beauty,
For yesterday is but a dream
And tomorrow only a vision,
But today well lived makes every yesterday
a dream of happiness
And every tomorrow a vision of hope.
Look well, therefore, to this day!
Such is the salutation of the dawn.

ABHIRAM NATARAJAN.