Karachi   ->   Sweden   ->   Karachi, again   ->   Dubai   ->   Bahrain   ->   Karachi, once more   ->   London and Leeds

Saturday, May 26, 2007

The Aha! Moments

I am not sure who coined this term. I first encountered it while reading Programming Pearls by Jon Bentley. An Aha! moment is when you have a sudden insight into something (it's more enjoyable when you had thought that you already knew that "something"). Some books of Scott Meyers also talk about it; see, for example, his article titled My Most Important C++ Aha! Moments...Ever.

It's weird how something becomes clear all of a sudden. I was going through the following problem last night (taken from Programming Pearls): You have to find an efficient algorithm to find the maximum sum of consecutive numbers in a series (which can include both positive and negative numbers). For example, the maximum sum in "-1, 2, 3, -4, 1" is 5 which starts at 2 and ends at 3. Any other sequence will include negative numbers and thus, reduce the sum.

A brute force algo for the problem would be as follows:
maxSoFar = 0
for i = [0,n)
   sum = 0
   for j = [i, n)
      sum += x[j]
      maxSoFar = max (sum, maxSoFar)
Its runtime is O(n2) which isn't good. How can we optimize it?

  • One first observation is that you can scan the array and keep counting until your sum becomes negative. If that happens you have to start over from the next index in the array.

  • However, your maximum sum might be the one just before your sum became negative. That is, without any negative numbers in the array, you can safely sum up all the numbers and declare the maximum.
If you keep thinking about this problem, and try out various examples by hand, you might encounter an Aha! moment :)

I once encountered a similar explanation by Kraig Brockschmidt in his book Mystic Microsoft:
Then suddenly, as if magnetically drawn by my intense concentration upon it, the singular question that I so deeply yearned to answer returned: “How do all these pieces of OLE 2 fit together?”

BOOM! A bolt of lightning flashed into my consciousness with tremendous power and in one timeless moment I simply understood OLE 2. Not just bits and pieces—everything! It was magnificent.

A scientific explanation of the phenomenon states that
It may not appear in the shape of a light bulb above your head, but researchers say "Aha!" moments are marked by a surge of electrical activity in the brain.

That is, there is more to "creative problem solving" than "usual problem solving." The creative part requires an insight, the ability to get out of context and look at the problem from a higher level/ different perspective. It won't be surprising if such problems require a different kind of physical activity in the brain, as suggested by the article quoted above.