Monthly Archives: April 2013

Uncategorized 3 Comments

Embrace Randomness

by

I think what makes life interesting is not predictability but randomness, I will give an example, On  Superbowl day  I met couple of friends at Crepevine in Palo Alo for brunch. While going back I took a wrong exit and ended up in the Stanford Campus. Now the roundabout there is almost a mile inside. Upon taking the U turn I noticed a museum midway that I had not on my earlier visits there.I pulled in and it turned out it was a museum established by none other than the Stanford family itself. I parked my car and went inside to see one of the best collection of artifacts and art that I have ever seen. (Added bonus entry and parking was free).So a wrong exit made my day richer.  Chance has a greater role in life than we like to admit.

Relating randomness to the Software world may seem strange but bear with me. The idea I seek to present is that random explorations may lead to serendipitous occurrences. Exploring things that you may not have encountered before goes a long way towards developing skills or adding new tools to your toolkit. For instance if you are a imperative style programmer, learning a functional language like Erlang  will expose you to a different style of thinking. If you  work with Mysql  then learning about a NoSql database like Redis will expose you to how unstructured data can be handled. It is of course difficult to predict how these random walks may be of immediate benefit but I think the real value lies in relating the disparate knowledge to a common thread. I think randomness is also what makes the Silicon Valley an interesting place to be. If you are a technology professional in the bay area chance encounters can lead to new opportunities or even just expose you to another dimension of the technology industry that you didn’t know existed.

One of the best ways to introduce randomness to your surfing habits is Stumbleupon, you can think of it as an gateway to the Internet which will recommend webpages based upon your interests. I came across PreyProject via stumbleupon where I went on to make my first ever open-source contributions which led me to eventually work at my current position. The other source for randomness I rely upon is hacker news.  In real life make use of meetup[not so random I admit]  or your favorite programming language’s user group[believe me even the most obscure language will have one here]. I think in case of real life the randomness begins once you show up which is not limited to showing up physically but also taking up projects that you care about. You like the girl you just met? Ask her out. So you want to write that killer app? Start working on it then, only then can randomness help you.

I think the charter I have laid down for myself is to embrace more randomness by showing up viz. building things I care about thus encountering problems that I haven’t seen before and in life in general. While I cannot vouch for all outcomes, I certainly hope it will be a interesting journey.

Uncategorized 4 Comments

Good Algorithms beat Supercomputers

by

It is good to remember why well designed algorithms matter.  I decided to experiment with the well known Fibonacci number. I have this sticky note plastered on my monitor at work.

“Good Algorithms beat Supercomputers”. Lets take a glimpse into why that is the case.
The fibonacci recurrence is defined as:
F(N) = F(N-1) + F(N-2), N>1

and F(N) = N for N: 0 or 1

This will lead to a series of numbers in order 0,1,1,2,3,5,8,….
Translating this to code we have the naive algorithm as:

public static long naiveFibo(int n){
   if(n==1 || n==0){
    return n;
   }
   return naiveFibo(n-1) + naiveFibo(n-2);
 }

However this naive algorithm suffers from a fatal flaw. As the values of n get larger, we end up computing fibonacci values repeatedly for multiple m<n. This is computationally expensive as n becomes larger.

eg. Fib(5) = Fib(4) + Fib(3)

Fib(4) = Fib(3) + Fib(2)

Fib(3) = Fib(2) + Fib(1)

Fib(2)  = Fib(1) + Fib(0)

We can already see Fib(2) being computed thrice and Fib(3) twice with this input.

So what now?
Lets do an optimization. This particular technique is called memoization. In simple terms what we do now is store  the fibonacci value the first time it is computed in an array at that index.  eg arr[5] will hold the value for Fib(5).
What this does is each time we want to compute the Fibonacci value for a given n we first do a lookup in our array. If it does not exist we compute and store it. While this is a fairly well known technique that is found in any decent CS Textbook. It is good to experiment and see the true power of well designed algorithms. Lets see how the code looks like:

public static long memoizedFibo(int n){
 if (arr[n] == 0) {
   if (n == 0 || n == 1){
       arr[n] = n;
   }else {
       arr[n] = memoizedFibo(n - 1) + memoizedFibo(n - 2);
      }
}
   return arr[n];
}

The client code follows in case you want to reproduce this on your machines:

public class Fibo {
  private static long[] arr = new long[100];

  public static void main(String[] args) {
  long startTime;
  double elapsedTime;
  for (int i = 0; i < 91; i++) {
    startTime = System.nanoTime();
    System.out.println(memoizedFibo(i));
    elapsedTime = (double) ((System.nanoTime() - startTime) / 1000000000);
    System.out.println("Time taken to compute Fib +" + i
+ " Memoized + " + elapsedTime + " Seconds");
}

for (int j = 0; j < 91; j++) {
    startTime = System.nanoTime();
    System.out.println(naiveFibo(j));
    elapsedTime = (double) ((System.nanoTime() - startTime) / 1000000000);
    System.out.println("Time taken to Compute" + j +"Fib Naive" + elapsedTime + "Seconds");
     }
 }

// Add Fibonacci methods here

} 

This seemingly simple change gives a massive speedup. I did some experimental runs on my 1.7 GHZ Core I5 with 4GB RAM.[Click on Image]


 Continue reading →