Vishwanath Krishnamurthi's blog

A blog on Java EE, clean code, open source and TDD

Why learn algorithms and data structures ?

with 2 comments

The question is – Why learn algorithms and data-structures ? 

and here are some thoughts. Probably you’d find this question answered in the preface of any algorithms book but anyway, here’s my take.

1) To not be constrained by the programming language for data-structure

Without a good knowledge of various data structures, it is easy to be constrained to thinking for solutions in terms of the data structures directly provided by the language.

If you were a Java programmer, you’d probably be thinking on solutions just in terms of what is provided in java.lang.util package.

Well, there’s lots more. Take for instance a simple need:  In a low end, basic phone, as the user types something, you’d like to present the user with “auto complete” feature. Thinking in terms of the data structures readily provided by the language /libraries doesn’t help much.

A simple trie  would help here. For another example, to think of any networking website that we use-

How does Facebook suggest you friends, How does LinkedIn tell personX is a 2nd level contact ?

A graph data structure helps here.

Or when there’s a steady stream of numbers coming in – and you want to maintain the largest 10 numbers. (You don’t have the
luxury of storing all the numbers and sorting them)  Min heap is the one to go to.

The list goes on..

2) Better hardware is not a solution

No amount of additional hardware is going to compensate for an inefficient algorithm. Super computer takes 1 week to sort a billion numbers using insertion sort whereas a home computer takes 18 minutes sort a billion numbers using merge sort.

Insertion Sort: O(n2)
Merge Sort: O(n logn)

3) You’ll come across some very interesting, non intuitive ways of solving problems

Given an array with n/2 distinct elements and n/2 copies of another element. Find the missing element.

Well, the normal solution we  would all think of is to do a linear scan through the array and to find the missing element after reading through  n/2+2  elements at the worst case. [ Worst case = all n/2 distinct numbers appear first in the array and then the number-which-repeats appears n/2 times]

Interestingly, this could be solved faster this way:


while(true) do

i = Rand.numberWithinRange(1 to n)

j = Rand.numberWithinRange(1 to n)

if(i!=j) and a[i]=a[j] then return i;

And the probability that the algorithm does not quit in 10 iterations is 0.1074 !

“Randomization” turns out to be an amazing practical way of solving some section of problems.

And to give a more “real-world”ish application for “randomization” -The randomized version of quicksort is one of the most practical/ efficient sorting algorithms !

Get ready to be surprised by lots of cool, non-intuitive-yet-amazing ways of solving problems

4) Refresh a little bit on probability, logarithm and some fun math

It’s interesting to get back to some math, – specifically on probability, expectations, logarithm..

5) Learn some interesting design paradigms

While learning different algorithms, you’d also be grasping the different algorithm design paradigms.

(Divide and Conquer, Greedy method, Backtracking, Dynamic Programming)

When there’s a new problem to be solved, this knowledge helps to come up with an efficient solution.

6) It’s a skill

Certain things are just “knowledge” – that could be learned-along-the-way when a need arises.

For example: There’s not really a need to know all the “MVC” frameworks out there. Knowing one is just enough. There’s a need to use some other MVC framework  ? Well that could be learned along the way..

But algorithms and data structures don’t fall into that category. It’s a skill, to deduce an algorithm for a problem  / It’s a skill to analyse the complexity and tell which algorithm is the better one / It’s good to learn in advance. Acquiring a skill is interesting, right ?

7) Quadratic complexity when O(n) solution exists

Without some learning of algorithms, it’s quite possible that we come up with inefficient solutions when an efficient one already exists !

8)  Understanding what’s behind the everyday tools..

Almost every tool that we use, day after day, applies some cool algorithms.

It can be an interesting exercise to find which algorithms are applied where !

About these ads

Written by Vishwanath Krishnamurthi

March 27, 2013 at 10:27 pm

2 Responses

Subscribe to comments with RSS.

  1. Great blog vishwa..this is hot discussion topic.https://twitter.com/ravi_mohan . This guy also agrees with you..Have you seen this stack exchange question?.http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed ..It is interesting

    sivaramom

    November 26, 2013 at 7:07 am

    • That’s a very interesting discussion indeed !
      Pick up just about any slice of software that we use everyday- there are so many core algorithms used behind it.

      Vishwanath Krishnamurthi

      December 11, 2013 at 9:01 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 120 other followers

%d bloggers like this: