Apps
Contact
Seminars
RSS FeedMarch 31st, 2010
Bang for the buck – Knapsacks in real life
Knapsack is such a fundamental optimization problem that computer scientists think everyone just has to understand what a knapsack problem is. But truth be told, last time I heard about a knapsack was either on Halloween, or many many years ago when Bishop Myriel put two more candlesticks in Jean Valjean’s knapsack. Other then that, I really have no memory of this apparatus. Computer Scientists think – oh this is just a bag to hold things in. Yeah right. In that case you would call it a backpack, not a knapsack.
A much more intuitive way to define a knapsack in today’s world would be to call it a resource allocation problem. Say you have a marketing budget of 5 million $, and say you have following marketing options and their paybacks (in million of new potential customers):
- Superbowl:: Cost: 3M $, Expected reach: 80 M people
- Radio ad campaign for 40 metro areas:: Cost: 800 K, Expected reach: 20M people
- TV non peak hour campaign: Cost: 500K $, Expected reach: 22M people
- City top paper network:: Cost: 2M $, Expected reach: 75M people
- Viral marketing campaign:: Cost: 50K $, Expected reach: 4M people
- Web advertising:: Cost: 600K $, Expected reach: 10M people
Which marketing campaigns do you choose? [This is called a pure 0/1 knapsack problem, as for each of these marketing campaigns you either select it, or you don't.]
Now consider, that in addition to the costs and paybacks of the marketing options, you also have data about how many marketing resources will be required to manage those campaigns, and since you have only 18 full time equivalents (including yourself) in the marketing department, that may pose some constraints as well:
- Superbowl: 3 M $, Expected reach: 80 M, 5 people
- Radio ad campaign for 40 metro areas: 800 K, 20 M, 6 people
- TV non peak hour campaign: 500 K, 22 M, 6 people
- City top paper network: 2 M, 75M, 2 people
- Viral marketing campaign: 50 K, 4 M, 2 people
- Web advertising: 600 K, 10 M, 1 person
Now, as you decide the marketing options, you need to make sure that you do not exceed the 5 M $ cash constraint, and also that you do not exceed the 18 people human resource constraint. This is an example of the “multiple constraints knapsack problem.“
March 27th, 2010
An old dice problem – probability of hitting 1000 in a running sum
So, you roll a standard six faced unbiased dice unlimited times, and keep your running sum. What is the probability you will hit 1000 (at some point of time).
Let us call that Pr(S=1000). Some base cases are easy to start with, and let us use q for 1/6:
Pr(S=1) = q = 0.166667
Pr(S=2) = q + q*Pr (S = 1) = q + q*q = q(1+q) = 0.194444
Pr(S=3) = q + q * Pr (S = 1) + q* Pr(S = 2)
= Pr (S = 2) + q* Pr(S = 2)
= q (1+ q)^2 = 0.226852
Pr(S=4) = q + q * Pr (S = 1) + q* Pr(S = 2) + q* Pr(S = 3)
= Pr(S=3) + q * Pr(S=3)
= q[(1+q)^3] = 0.264660
Pr(S=5) = q + q * Pr (S = 1) + q* Pr(S = 2) + q* Pr(S = 3) + q* Pr(S = 4)
= Pr(S=4) + q * Pr(S=4)
= q[(1+q)^4] = 0.308771
Pr(S=6) = q + q * Pr (S = 1) + q* Pr(S = 2) + q* Pr(S = 3) + q* Pr(S = 4) + q*Pr(S=5)
= Pr(S=5) + q * Pr(S=5)
= q[(1+q)^5] = 0.360232
This is the point from which we deviate from this script, because Pr(S=7) does not have a sequence of length 1 as its component. Instead, we write the following recurrence relation, which applies as long as N > 6:
Pr(S=N) = Sum of probabilities of all distinct sequences which lead to N. We can distinguish the sequences based on the last dice roll, which can be {1..6}.
Pr(S=N) = q * Pr(S=N-1) + q * Pr(S=N-2)+ q * Pr(S=N-3)+ q * Pr(S=N-4)+ q * Pr(S=N-5)+ q * Pr(S=N-6)
= q * Sum_{i = 1 to 6} {Pr (S=N-i)}
That is, Pr(S=N) is the arithmetic average of previous 6 terms of the series. So, it is easy to see that Pr(S=N) is a series that is stabilizing. Even using the plain old Excel, the first few terms of the series are:
Pr(S=7) = 0.253604395
Pr(S=8) = 0.268094017
Pr(S=9) = 0.280368945
Pr(S=10) = 0.289288461
By 100, the series stabilizes to Pr(S=100) = 0.285714286. That is also the value for S=1000, and hence the answer to the question above.
It is easy to miss the observation that 0.285714286 is the same as 1/3.5, where 3.5 is the average of numbers on the dice.
By weak law of large numbers, if a dice is thrown k times, then the expected value of the sum will be close to 3.5 * k. The probability that the sum will be a specific number would then be 1/3.5.
March 26th, 2010
Product design and innovation
Once in a while, I do get this question: “So, what is it that you do do?”. Now, I could say something like product development, but since my Eclipse IDE stopped working back in 2007, I haven’t gotten around to fixing that (yet), that kind of answers that one. Perhaps the clearest answer is this – conceptualizing software products that I believe can help people solve their problems. We can dissect that line word by word:
- conceptualizing: I refer to it as “conceptualizing”, as the design and development is usually done by a different team.
- software products: Yeah, that is the space I am playing in, at least at the moment.
- “I believe”: Any product designed is a gamble, and it is best to acknowledge that as such, upfront.
- help people solve their problems: This is obviously at the core of building a product. The problem that the product will solve is usually the best indication of the success of this product. Is this problem worthy of solving? How much of a problem really is this problem? How many people may have this problem?
There are 3 well known rules of engagements when creating products:
- Ask the users (but sometimes not believe them): Since the products don’t exist yet, the users have some ideas, but some of them may be too specific to their unique problems. So while the users’ first few sentences are of huge value in describing the problem, detailed thesis are not. It is best to engage users in small but frequent sessions so they can react to latest version of the product. Also, this avoids the pitfall of solving a user’s specific challenge on a specific day. We want to solve REPEATING problems, not one offs.
- Not worry about the so called “competition”: This is an important concept. No matter what you come up with, people will try to box other products and label them as your competition. This is usually done with the best of intentions, in some cases just so as to explain your product. But focus on the users with problems, not other products that they could hypothetically use but are not using.
- Don’t overvalue innovation over execution: As Facebook and many other successes have shown, it is a fallacy to think that every success comes from making something new. Not necessarily true. Any new product usually has 3 kinds of features: (i) Features that are new, (ii) Features that are old, and (iii) Features that exist in a different form in other products. Counter intuitively, usually it is the last category – the features that exist in other products, but in less usable or functional form – that is the best reason for the success of the product. (Second in importance are the features that are old.)
March 23rd, 2010
Slacker Radio for BlackBerry (TMobile 3G) – Review
Today when driving from home to work, I tested the Slacker Radio on my Blackberry Bold using TMobile 3G network. Very pleasantly surprised by the audio quality that the device was able to maintain as I drove for about 30 minutes in the DC metro area. Was definitely better than the quality that I get from YouTube using Blackberry browser, but that could easily be because of it being audio versus video, and also because of more predictability coming from a radio channel.
Naturally, I was interested in knowing the programming language and the environment that this application is written in. Slacker software forum is the perfect starting point for this. I am currently downloading the Blackberry SDK from http://na.blackberry.com/eng/developers/, and am keen to test out this process, even if I only scratch the surface.
Btw, if you are looking for a Slacker review that focuses on the application details itself, CNET has a good review, which is available here. As always, Jessica Dolcourt does a fine job.
March 22nd, 2010
First Lady Michelle Obama’s speech at GMA meeting
Admittedly, I was attending the GMA meeting due to my role in PREDICT – the US FDA’s admissibility system, still, it was a privilege to hear the first lady Michelle Obama’s speech at the GMA meeting this past Tuesday. She spoke very eloquently, and really had a very inclusive – “come together” – kind of message. It was quite an achievement to talk about junk food and calories in front of an organization such as GMA, which has Coke/Pepsi and major snackers as its members. After the event she was gracious enough to shake hands with all the people sitting in the first row.
I tried to take some pictures, but I had forgotten my camera and was just not familiar enough with my Blackberry Bold. Still, this is what I have. In all 3 of the pictures, you will really have to strain hard to find even where she is, and that is why I should be given a medal for the WORST PHOTOGRAPHER EVER. 
.
A much better picture of hers at the GMA (taken by a pro!) can be found her: http://www.rodale.com/michelle-obama-speech-gma
