The last weekend was spent in Mysore, sprawling on a comfortable couch and watching 3 Idiots on my uncle’s ultra-large screen TV. A brilliantly-made movie, it made me reflect on an incident that occured while I was at BITS, doing a course on algorithm design.

I was lucky enough to be taught by a professor who actually knew what he was talking about–understanding his domain deeply in a way that would withstand unbounded questioning. (I’ve slowly come to realize his is indeed a rare breed)

So, one day he walks into class and asks “when can you use the Divide-and-Conquer algorithm to solve a problem?”. And we all pounce on this easy question “when you can divide the problem into sub-problems that you can solve”. And of course the professor isn’t satisfied (we should have known better– he never posed easy questions to while away time).

In typical classroom fashion, we began to add more jargon to the problem, mentioning details such as finding non-overlapping sub-problems and suchlike (at the Wikipedia, someone like-minded has added a considerably detailed entry about this method algorithm).

After letting us listen to our voices for sometime, he gave in. A divide-and-conquer only works if the solutions to sub-problems can actually be combined to yield the solution to the original problem. Missing this crucial proviso would make nearly every problem solvable by D&C. Say, for example, the knapsack problem, or even, the map-coloring problem (i.e. coloring every country in a map such that it has a different color than its neighbor). In this case, we could just take each country separately, color it with some color and “solve” by coloring all its neighbors with a different color: combining these “solutions”, of course, is the problem.

Besides the obvious “coverpage-value” of understanding D&C better, I feel this lecture helped me mold the way I think in a subtler way.

More often than not, humans tend to concentrate on the details of a particular problem, framing it and reducing it to something that is soluble. Sure, this is a great way to solve problems most of the time. But every once in a while, this method scheme fails, and we discover that binary search is broken.

Over the past year or so, I’ve consciously been trying to “break out” of the details occasionally and it’s been very interesting. I haven’t really made any path-breaking discoveries, but it’s fun, and I’m hoping it will be profitable.

If you don’t already, you should try it too!