Skip to main content

Comparing Algorithms

I recently mentioned that MIT OpenCourseware project started hosting Video/Audio lectures as well for some select courses. Thats an excellent opportunity to go to MIT and take a class without ever leaving your home.

I never studied formally about Computer Algorithms. So I started taking the course : 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005. After spending so many years in Software Development, I must admit, I have not much to take away from the first 1 hour 20min class, but here are some thoughts and notes on the size of input.

[Source:Wiki] In theoretical analysis of algorithms it is common to estimate their complexity in asymptotic sense, i.e., to estimate the complexity function for reasonably large length of input. Big O notation, omega notation and theta notation are used to this end. For instance, binary search is said to run an amount of steps proportional to a logarithm, or in O(log(n)), colloquially "in logarithmic time". Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called hidden constant.

The key aspect of Asymptotic analysis is about estimating the rate of growth of required resources to achieve a function, particularly, to estimate the complexity function for reasonably large length of input. If the size of input doesn't qualify for this reasonably large length of input then the analysis just doesn't apply. Then the big question is about knowing this size of input, to be able to apply the concept for each such algorithm. This is the missing piece of the puzzle, often ignored. Often, it was always argued that one algorithm is much better than the other, as that is what being taught in class room or mentioned in academics.

For general problems like sorting, we might get an extensive analysis available in books and papers. But when it comes to problems that are specific to a domain, there is not much analysis available. We must do on our own to find out what is a resonably large size of input means for our problem. If we can learn how to do this, then we can apply our understanding of Asymptotic analysis in real life problems.

This is the reason we might have multiple algorithms in a solution rather than having just the 'BEST' (as per some CS grads) algorithm.

The example being discussed in the class was about sorting. Two algorithms have been compared: Insertion Sort and Merge Sort. Watch lecture 1 here. Link to Thought Garage » MIT Video/Audio OpenCourseWare

Popular posts from this blog

You Are What You Think People Think About You

There are about 6.7 Billion people in this world that we know of.  Whether you believe in ‘Creation’ or ‘Evolution’, this human race started with a tiny number. It is quite amazing to see how fast it multiplies. What is more amazing is that every single individual in that 6 billion crowd is born ‘unique’.  Quite literally, you are born to be one in a billion, whether you believe it or not. “ This was the Introduction to my latest and last speech in Toast Masters club, ‘One in a Billion’ as part of International Speech contest. 
As much as I believe that each one of us can be that 'one in a billion' personality, I admit the reality as I perceive it and some times feel alone in that belief.
A famous quote says 'You are what you think'. It is also true that 'you are what you think people think about you'. If you think people think you are smart, then you act smart and become smart. If you think people think you are dumb, you will become dumb even if you are not, a…

Cooking looks like an unforgiving art

When you are writing software, you always get a second chance. In fact, lots of chances to get it correct. You have compiler warnings, failed test cases and some times crashes alert you that something is not right and will give you a chance to correct. And you get literally unlimited chances to apply those corrections. 
Well, cooking looks to be totally unforgiving in this respect and on any given day, you may get just one chance to get it right. If you fail, you fail. Try again right away if you have patience of starting it all over. Or start over some time later or next day. But not much of a second chance to correct a mistake. 
More ruthless, when it comes to salt. If you put just a little more, even a tiny little more, it never hesitate to show what it got. Totally ruthless. End result will be a failed dish that no one will be able (and/or happy) to eat. And most dishes, you may not be able to add something little more to offset it.

Little trick I learned the hard way, start on …

Did NDTV Just Twisted Words?

I have recently spotted quite a few places where NDTV title doesn’t exactly say the same as the details in the article says. Lost in translation? or just plain twisting for journalistic sensationalism?Title says “'AAP doesn't treat women as humans,' says founder member Madhu Bhaduri as she quits”, but the quote in details says, slightly differently: “In this party, women are not considered humans” (see the text highlighted).Source : NDTV.comYou may say, they effectually mean the same thing. Is it? Even if they mean the same,  Why not use the same exact phrase in both places?