Dynamic programming – taking the curse out of recursion!

I think most of the programmers are familiar with recursive code and almost all of us have solved recursive problems like Fibonacci series or Factorial during our CS courses. We know that if try higher numbers, the code crashes with StackOverflowError.

Dynamic programming or DP as it is popularly known is a blessing for many problems requiring either recursive or iterative algorithms. I am not going to go into the details of DP as such, you can easily find good information about it on Wikipedia or read about it in any one of those excellent tutorials available on the Internet, one such example can be found here on CodeChef.

In short, Dynamic Programming is an approach of solving complex problems by breaking them into several smaller sub-problems, where the sub-problems are overlapping sub-problems. It can make lot of recursive problems much more efficient. Dynamic Programming approach is similar to recursive programming, however in dynamic programming the intermediate results are cached/stored for future calls.

If we consider recursive programing for Fibonacci series, – computing the nth number depends on the previous n-1 numbers and each call results in two recursive calls. Thus, the time complexity is –

T(n) = T(n-1) + T(n-2) = O(2n).

In other words, as we increase the Fibonacci number, the time taken to compute that Fibonacci number increases exponentially!

On the other hand, if we use Dynamic Programming for Fibonacci number, since the earlier results are cached, we simply have complexity as –

Time Complexity = O(n)
Extra Space = O(n)

In fact, it is fairly easy to reduce additional space for Fibonacci number by just storing previous two results instead of storing all the previous results.

In plain English, it means that Dynamic Programming can drastically reduce the time taken to compute solutions that require several recursive/iterative calls. As an experiment, I wrote small Java code that computes Fibonacci number using recursion as well as Dynamic Programming. Do watch the results posted below this code to know respective time taken while computing the 50th Fibonacci number. You can try this code with different numbers on your own computer as well and see it for yourself. DP rocks!!! :-)

public class FiboDyna{
    long fibo[] = new long[200];
	
    public long fibonacci(int n){
	if (0 == n){
		return 0;
	}
	if(1 == n){
		return 1;
	}
	//return result from cache
	if(0 != fibo[n]){
		return fibo[n];
	}
	fibo[n] = fibonacci(n - 1) + fibonacci(n - 2);
	return fibo[n];
    }
	
    public long fibonacci_rec(int n){
	if (0 == n){
		return 0;
	}
	if(1 == n){
		return 1;
	}
	return fibonacci_rec(n - 1) + fibonacci_rec(n - 2);
    }	
	
    public static void main(String args[]){
	FiboDyna fd = new FiboDyna();
	long start = System.currentTimeMillis();
	System.out.println("Dynamic fibonacci 50 = " + fd.fibonacci(50));
	long finish = System.currentTimeMillis();
	System.out.println("Time taken for Dynamic Fibbonacci = " 
                            + (finish - start) + " ms");
		
	start = System.currentTimeMillis();
	System.out.println("Recursive fibonacci 50 = " + fd.fibonacci_rec(50));
	finish = System.currentTimeMillis();
	System.out.println("Time taken for Recursive Fibbonacci = " 
                            + (finish - start) + " ms");
    }
}

dp-fibo

I am hoping to use it for some non-trivial, real-life problem whenever I can, and if I manage to do that successfully, I’d definitely post it here!

Career Concepts & Career Paths

The Four Career Concepts

The Four Career Concepts

I had published this article on another blog, but I thought it would be relevant here as well, so I am adding it here.

Career Concepts & associated Career Paths is an interesting theory based on the work of Michael Driver and Ken Brousseau of the University of Southern California. When I first read it, my reaction was also similar to what Mr. Clawson describes – I was ecstatic that there is a “name” and research that supports things I’ve felt intuitively for a long time. There was this certain “Eureka…” moment when I figured out my own type (Spiral-Expert, more in favour of spiral) and ever since, I think I have better insight when I listen to people talking about their own career aspirations & goals. There are primarily four career patterns based on how people choose their profession, roles and plan their career. These four patterns are listed and discussed briefly below.

  1. Linear (L) – This is probably the most familiar and well-accepted career concept, and usually associated with material success. It can be thought of as a career ladder with increasing power, status and money. For ‘linear types’, the primary work motivation is increasing power & status. This is the conventional upward movement and you’d often find ‘linear types’ climbing corporate ladder and aspiring to be the top executives. Unfortunately, often this is perceived as the only career path by senior managers (who usually happen to be ‘linear type’ themselves) and hence by most HR professionals as well.
  2. Steady-State Expert or Expert (SSE) – This can be thought of as a ladder of few steps and then a steady straight line indicating high level of expertise. They are not motivated much by status, power (such as promotion) but they are driven by perfecting their skill & craftsmanship/expertise. They derive pleasure in mastering their craft and becoming expert in their own field. You can think of top medical professionals, specialist and super-specialist doctors, top lawyers and architects as examples of spiral types.

    Sometimes, these experts may follow linear career path and accept higher position as a manager as that might be the only available way of earning more money in some organizations. The might do this due lack of self-awareness or due to common, societal ‘linear’ definition of success. But a true expert (individual with dominant SSE concept) may not fit this managerial role and may eventually fail. It is crucial for good organizations which thrive on superior technical talent (such as software development companies) to provide alternate paths of growth to recognize and reward these technically talented experts.

  3. Spiral (S) – These type of individuals are not much motivated by power, status but they are driven by learning & knowledge. Unlike SSEs/experts, they are not interested in perfecting their skill or expertise beyond a certain level, once they achieve certain level of success or expertise, they seek new challenges and learning. They are true learners, and they are willing to give up their position of power & status to experience the steep learning curve. They find their own underlying purpose through series of different roles and work (across industries if required) that they may undertake in their life. They are creative and motivated by personal growth. They bring deep insights and knowledge to cross-functional roles and prove to be a very valuable assets to organization that could offer them interesting & challenging work & roles. You are likely to find knowledgeable individuals who have changed their work, industries or careers as ‘spiral type’.

    They could be misunderstood as Transitory types, but they are quite different in the sense that they are motivated by the work they choose and they are driven by personal growth, knowledge & learning.

  4. Transitory (T) – These types of individuals are not motivated by work, though they may be reasonably good at it – but work is not their primary motivation. They’d work as long as it is required to earn enough money and then do what they’d rather be doing. This may include travel, backpacking, photography on positive side or some addictions like alcohol, drugs on the negative side. Their careers typically include some periods of work & earning money, followed by long fun breaks enjoying what they love doing – from mountaineering to whatever exotic hobby they might be interested in. Many freelancers taking up short-term jobs are and following their hobbies are often ‘transitory types’. I have few freelancer friends who follow this pattern, working on small assignments to earn money and spending rest of the year with their hobbies, ranging from wildlife, travel to various forms of music.

Many of us can broadly identify our type based on the description above. However, James G. S. Clawson has developed a Career Concepts Instrument that could be very useful to find out your own type based on few simple questions. You just need to answer the questions honestly based on your own views about the career, there are no rights or wrongs here, just answer the questions and based on the score of the instrument you can find your dominant concept. Many of us have combination, I happen to Spiral-Expert myself with slightly more inclination towards spiral. This instrument also contains required explanation of all these four types with their associated career graphs plotted on Time Vs. Status-&-Power axis. Here is small excerpt from Mr. Clawson’s article –

Society defines success, typically, in terms of wealth and power. We read about the rich and famous in the newspapers and biographies, and see them in the news and in films. It turns out though, that left to their own devices, people will choose a variety of career paths, only one of which really leads ever upward. Professors Michael Driver and Ken Brousseau of the University of Southern California have identified alternative patterns that people seem to choose.
……
Driver and Brousseau’s insight with regard to careers and success is that they recognized that not everyone is motivated by power and wealth. Further, not everyone is suited to navigating careers oriented toward power and wealth.

Most people who make hiring & promotion related decisions are not even aware of these career concepts and their role in career success. So they continue to glorify linear career path and continue make poor, often prejudiced decisions for themselves and their organizations. I really hope more and more decision makers & HR professionals become aware of this to allow to them to make better decisions.

You can read complete Career Concepts Instrument here.

This instrument by Mr. Clawson is developed to give quick view of these concepts, if you are really keen and curious about this theory, you can get the full instrument at Decision Dynamics LLC. Once you have taken the test you can read detailed information about these four career concepts from the original paper published by Kenneth Brousseau & Michael Driver. It also gives details about various combinations with typical career options for those types.

Read more about Career Concepts here.

I hope this post and suggested instruments, articles would help you in figuring out more about your own career concept and aspirations.

(The diagram is my quick-n-dirty illustration based on Mr. Clawson’s article)

Gas Lighter & The Design Of Everyday things

In India, it is difficult to see different variations & designs of some common stuff that we use daily. Though FMCG sector has seen many innovations & creativity in the last decade, the mundane daily items such as gas lighter remain mostly the same. Most of them use a piezo-electric crystal, and rather hard-to-press trigger/button to generate a spark. Recently I had a minor thumb injury that made it very difficult for me to use a regular gas lighter (the chrome plated one that you see in the photo). That’s when I started looking for a new gas lighter that we had some 6-7 years ago but it stopped working about a year ago or so. We were using the regular one since. This thumb injury prompted me to look for this again with renewed vigour & purpose. I’ll skip the long story of search for this lighter. I thought increased purchasing power of people might have triggered more sale for this gas lighter, but as it turned out 99% of the shops that I visited (in Pune) were not even aware that one such gas lighter was being manufactured. Finally, I managed to get it one shop. I guess, this was the same shop where we had purchased it for the first time. (The grey one that you see in the photo)

Gas Lighter

Gas Lighters

I was quite relived as it allowed me to use the gas lighter without much pain to my injured thumb. Moreover, it was much more convenient for our old cook as well. She found it difficult to use the regular one. This actually prompted more thinking about the design – design of this gas lighter. Slowly, I observed that it was difficult for older people to use the regular gas lighter primarily because of the hard-to-press trigger/button. The gas lighter that I purchased has a switch similar to a simple push-button, making it extremely easy to use. It uses a single AAA sized battery and the gas lighter itself lasted for 5+ years as we had experienced with our first one. The finish and look of this lighter is much better than the regular one as well. It’s a simple device – but well designed and makes it extremely convenient for everybody.

The design of everyday things

The Design Of Everyday Things

In his book The Design Of Everyday Things Donald Norman talks about this – thoughtful design. Understanding user’s real requirements beyond all the conventions and perceived user demands could really take the product to a different level. Designs that understand this psychopathology of everyday things and follow intuitive, easy to use approaches for their products are most likely to have greater user acceptance. During my short course at IDC, IIT Bombay, we had an opportunity to design few such everyday things – from a simple refrigerator switch to making toys for kids, followed by some thought-provoking discussion with our professor Anirudha Joshi. There are some invaluable insights about design that we have gained in the process. It is fascinating to see how design has its own subtle yet powerful language that speaks to us without words. Imagine how would you open a door that has a short vertical handle? Imagine how would you open a door that has a large horizontal handle? In both cases, assume that there are no words, no PUSH/PULL written on the doors. Just try doing it in the air right now and you’d realize how we respond to such simple design elements. The more you learn those design nuances, the more intuitive & useful your products would be – be it software or any other device such as this gas lighter. Design is lot more than making stuff look good!

If it hadn’t been for my injured thumb and all those observations that followed afterwards with older people and their use of a gas lighter; I think I wouldn’t have ever appreciated this product design properly. Despite its high cost (close to ₹ 300 as compared to ₹ 70 to ₹ 125 for a regular gas lighter), I believe this gas lighter has a potential to sell lot more units if it is marketed and distributed with little more efforts. I hope the manufacturers will do it!

DISCLAIMER: I am not associated with the manufacturer of this gas lighter in any way. :-)


Update: 27 Oct 2014

Found this apt quote by Steve Jobs – Perrrrrrrrrfect!!