Vishwanath Krishnamurthi's blog

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

Posts Tagged ‘data structures

Why learn algorithms and data structures ?

with 4 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 !


Written by Vishwanath Krishnamurthi

March 27, 2013 at 10:27 pm