# Good Algorithms beat Supercomputers

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");
}
}

} ```

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]

# Being Craftsman

What does the word craftsman evoke? For me it is images of toolmakers building watches, shipbuilders working in tandem towards building massive vessels and of course developers cranking out code.

Progressing as a craftsman is a hard task. I think there are three key essentials for success.

1. The Guidance of Master Craftsmen/Women(henceforth referred to craftsman for the rest of this essay).

2. The burning desire to build, tweak and continuously refine.

3. The tenacity to work hard through the not so interesting parts.

Self learning is a good thing, but in the company of master craftsmen one can make giant leaps. As I rediscovered, working with the best evokes the desire to build better. There are techniques one can pick up by observation and osmosis.

While I was writing this post I rather serendipitously came across a documentary called “Jiro Dreams of Sushi” .(Available as of 30th Dec 2012 on Amazon Prime and Netflix streaming.) Jiro is a master Sushi chef who runs a Michelin 3 star restaurant in a Tokyo Subway.(Earning 3 stars from Michelin means that the place is so good that it is worthwhile to visit the country just for that restaurant.) Jiro at 85 years plus is someone who is at the peak of his craft and still aims to surpass it each day.

What resonated strongly was the idea that to achieve success you need to be so good that you cant be ignored. Further building on this is another idea that you need to satisfy your work rather than rooting for some dream passion. Satisfying the work that is given to you is a stepping stone towards building expertise and thus uncovering a deeper satisfaction of the work that you do.

It was also enlightening to see the tough regimen that aspiring sushi apprentices have to undergo before they can even handle fish often running into many years. Jiro’s son Yoshikazu a master Sushi Chef in his own right at 50 years still gets critiqued by his demanding father. The other takeaway was simplicity and the ability to develop an expertise in a niche area. There are no shortcuts and one has to commit to a lifetime of learning.

Finding a master is not easy. Why should anyone spend time to critique you? This is not a question that I have an answer for, just theories. Ultimately one needs to offer something of value. Finding a way to lighten your potential master’s load or solving a problem for him is one way to form a symbiotic relationship. The other motivation I think comes from great craftsmen themselves who want the craft to progress. In an environment like a Software company or even a Sushi bar like Jiro’s it is imperative to train apprentices to take upon future roles as craftsmen themselves. This is pure economics at play once the enterprise needs to run at scale.

There are times when apprentices get assigned dreary tasks. I think the most successful craftsmen have gone through this phase, tenaciously completing the assigned tasks, learning the domain along the way.Many problems are apparent only after doing the grunt work first.

I wish you a lifetime of learning. I would love to know  how you became a Better craftsman or even a Master Craftsman 🙂 ?

# The Art of Debugging

It was a sunny day, I stepped in my car and started out for work. Within the first hundred feet of the car moving, I heard a muffled but regular “thup a thup a thup”. I stopped the music and it was still there, I pulled over and got out of the car. Did a quick visual, checked if my bumper was hitting the tires, saw nothing amiss and started again. The sound persisted “aargh!”. I pulled over again. I saw a elderly gentleman approaching, great luck. I lowered my windows and asked if he could see any obvious flaws as I would attempt to move the car slowly. Hoping for a affirmative, I was aghast when he gestured to me that he was extremely hard of hearing.I got down again and started looking at the tires again. Then there it was stuck on my front tire, some kind of a poly wrappng material. Each time the tire  rotated the portion that wasn’t stuck was hitting the area above the tire. I took it out and problem solved. I had just completed debugging my car.

In fact debugging is very much a part of programming as it is in daily life. best advice I got out of college was “learn to debug”(a). It would be analogous to doctors figuring out what is wrong with a patient or a mechanic finding trouble with a car. The goals similar, but the objects and tools employed different.

Java being my primary language I started out with these excellent eclipse debugger videos. http://eclipsetutorial.sourceforge.net/debugger.html

More recently I’ve been using winpdb(http://winpdb.org/) for my Python exploits.  These days I debug, a lot! I would think the best programmers will be extremely good at debugging as well.

Some of the techniques I’ve come to employ are:

1. Reduce the problem space.

2. Use print statements(for localized problems).

3. Use Debuggers  (which was my original intent in asking the elderly gentleman)

4. Logs: Logs give a long term state of the system when turned on. Of course its very easy to have them running into millions of lines which leads me to point 1. again.

The other use of debuggers I make is to understand the behaviour of unfamiliar programs. When a reading is not sufficient, It is quite handy to spin up the debugger and step through the program seeing the state of the data that it manipulates. I call it an art since no single technique is guaranteed to give a solution. How to debug problems consistently with a low time investment is certainly an art. I would love to know the techniques that you employ to debug programs and life in general.

a.What is Debugging? At its essence given a system with x as a known and expected behaviour and y as undesirable behaviour, the task of reconciling the difference and finding the root cause is debugging.

# What have you built recently?

I decided to learn python recently. Going through the usual motions of starting with variables to moving to loops, something did not seem right.

This exercise was not fun. So I said screw it, I want to build a tictactoe game in Python.

https://github.com/hvd/TicTacToe-Python

The rest followed. It was hard no doubt having to learn new paradigms, but having a clear goal in mind helped in gathering the relevant information.

I think a massive shift is needed in how we learn from kindergarten right to grad school and even later in life. Learning by doing is certainly the best way in my opinion. Yet, that is not the way we think natural.

Think about it, how did you come to speak the language that you do today? Did you learn by first learning the theoretical basis and the grammer or by listening and being absorbed in an environment that literally leaked that language (your family).

Building a simple game like TicTacToe taught me valuable lessons.

1. Rome was’nt built in a day, the same goes for software.

2. Gaining skills takes time, Be patient.

3. There is great joy to be gained from building something from scratch and that in itself is reason enough to do it.

4. This is a form of deliberate practice. Pushing yourself beyond what you can do currently is deliberate practice. Building something that you havent yet will invariably involve some aspect that will push your limits.

I still haven’t decided what I will build next. I would love to know what you have built recently?

p.s While building something is natural for programmers, architects, carpenters… There will be analogous situations for people in other professions when equated with deliberate practice. Remember 10000 hours is the magic number to hit.

Cheers!

# The Essence of a Software Developer

I do end up spending quite some time after work thinking what is it that makes a Software Developer great? Being a newbie in the craft this is a very pertinent question.

The starting point of course is my mentors. They just seem to get it, while I will take time to come to  a solution, my experience has been whenever a codebase question pops up, all it takes is one glance or  maybe two for them.

Next come Messrs Spolsky and Yegge. As far as dev potential goes, the Spolsky school of thought prefers the Smart and gets things done while the Yegge one is all out for the Done and gets things Smart. The latter is a recent discovery(for me) and I think the question now is How does one move from Smart and gets things Done to Done and gets things Smart.

Getting things smart, now that is something. Some of it is inbuilt agreed, but what we(newbie devs) do have in our control is deliberate practice. Being a follower of study hacks, we do want to keep learning new things which may be few in quantity but master them.

Some of the things I am working on:

1. Learn to type(fewer glances to the keyboard is a big win!).

2. Start off your day with a sort, flex those algorithmic muscles you have .

4. Open Course ware: Top universities have made entire Computer Science courses available online, see what piques your interest and go for it.

This is my favorite for data structures:

A lot of knowledge will be assimilated from your peers or mentors, that is the nature of  Software. My understanding is there is no magic bullet, It is with time and sustained effort the top developers are truly great. Going through the pain as I am now, stumbling out from ignorance into light, I still have to discover what is it that constitutes the essence of a Software developer. For now I am hungry and foolish.

# Day in the Life of a Software Developer

1.Wake up, Check email to see build status.

2.Get ready, reach work(which really is 3 feet away if you are working from home).

3.check email again for major changes to codeline.

4. Start Eclipse(or suitable IDE, Visual Studio maybe , EMACS or VIM if you are hardcore linux)

5. Resume coding on feature you have been thinking about in your dreams.

6.Always be vigilant whether the tools you are using are licensed, free as in free speech, free beer or

both.

7. Meetings (May vary depending on if you are Agile or some other variation)

8.Lunch (Grab a sub or something else and get back to your cube)

9. Talk to colleagues in the break room intermittently about the feature/codeline.

10. Run automation tests against code.(varies)

11.Tea/Coffee + Sunlight break at 3:00 . Get Tea and step out in the sun, think about the code you have written and the code you are going to write.(Believe me Sunlight does wonders for Programmers)

12.Back to coding.

13. Check in code before leaving (again varies)

14.Reach home and VPN In the n/w.

15. Go biking or whatever it is that you do.

17. Have a nice dinner(not necessarily cooked by you) while watching netflix streaming,youtube.

18.Prepare for next day(By now you do realize you are in a infinite loop)

# The Case for Open Source Development

One year ago, I was fresh out of grad school  having secured a Master’s in Computer Science. A Master’s program certainly made me delusional as far as the job prospects were concerned. I strongly believed that seeing my  credentials as someone who could do research getting a job would be a piece of cake. This was towards the end of 2009, when the effects of the recession were still in play.  I ended up working for startup x doing uninspiring work.

Mid 2010 as I was stumbling, for those unfamiliar perusing http://stumbleupon.com. I came across http://preyproject.com. It was something that immediately caught my attention even though the webpage was in Spanish. Running it through google translate I quickly realized this was something I cared about, A geo-tracking software for Laptop’s, mac’s and cell phones. Discarding all my inhibitions I mailed the developers Tom and Carlos asking if they needed any help. They were kind enough to respond positively and I found myself involved in a Open Source Project based out of Chile.During the course of my interaction with Carlos, I became acquainted with git, Blackberry app development and most of all rekindled the spark of software development in me which was missing since high school.

I moved to California and now write extremely inspiring server side enterprise software. Open Source Software is an idea that cannot be ignored. My experience with PreyProject helped me deliver at BMC by engaging with the Open source Community which is one of my responsibilities in addition to building cool stuff I can’t write about. At BMC I am still learning the various facets of Software Development being surrounded by amazing Developers and working in an Agile team.

Prey took a back seat but I was determined to deliver on that front too. Last weekend I pushed onto github the “Lock” module for the Blackberry version of Prey. The Lock module is essentially a global UI that is triggered onto a mobile screen by a push from the server side, which disables all actions on the blackberry and can only be unlocked using a passphrase set at the serverside. Furthermore, the cool thing is that since Prey runs as a service on the device turning it off and then on simply means the service starts again with the device, and if the lock attribute is set at the server side the Lock will be in play again!

Today I ported the code with the Lock addition on my Blackberry Curve. After testing functionality and seeing it work, I was filled with Pride and Joy. Pride that I had created something of value, Joy that I had created something beautiful and  that I had created something that I really wanted to do. I created a feature which may well be used in millions of devices. But even if it isn’t that wouldnt diminish my joy one bit.

One may well say there is no financial gain out of this exercise. I was reading Pete Sampras’s autobiography the other night and he said he must’ve hit a tennis ball at least a million times before he ever set foot on court in his first major match. If you have read Malcolm Gladwell’s Outliers his hypothesis is to gain expertise in a field One must spend at least 10000 hours engaged in tasks of higher complexity than the previous one. 10 years to become a expert software developer as outlined by Peter Norvig. I might have come late to the party but I sure do intend to be an expert Software Developer with time. Good Software Developers are Craftsmen or Craftswomen and what makes them so good is practice. Open Source development is a very effective way of engaging with the best developers across the globe and creating a meaningful impact by doing  something you like to do. Furthermore Open Source software is a unique repository of millions of lines of code open to inspection by anyone. Read code, write code then read some more code.

So stop for a moment, Find a project you like on github or sourceforge. Join a project, Drive a project but most of all remember the time when you were a kid, when anything was possible and create something just for the Joy of it.