For a while I’ve been reading programming pearls…Then I wanted some change so picked up the beauty of programming (again). This time it went pretty smooth, due to the fact that’s the second time I read it – although the first time I didn’t really look into all the details…Anyway I want to blog about two dynamic programming problems:

Problem: Discount
Note:
this is a simplified version from the book…

Problem:
suppose you need to buy N books. The price is $p / book, and if you order several books together in an order you will get corresponding discount as following:
1 book – d1
2 books – d2
3 books – d3
4 books – d4
5 books – d5
Please compute the minimum money you have to spend.

Solution:
- Let f(n) to be the minimum money to buy n books.
- f(n) = min(
f(n-1) + p*d1,
f(n-2) + 2*p*d2,
f(n-3) + 3*p*d3,
f(n-4) + 4*p*d4,
f(n-5) + 5*p*d5
)
- The initial values (or the termination conditions if you see it as recursive…) are first 5 items.

Problem: Backpack
The official name should be ’0-1 knacksack problem’ if I googled it correctly…The problem is suppose you have a bag that can afford weight w, and you got n items that values are v[i] and weight are w[i], calculate the maximum value you can put in your bag.

Solution:
The key here is to identify the variables for dynamic programming. So if we look at this problem as f(n, w) where n means n items and w means the weight capacity is w, then the model is obvious:
f(n, w) = max(
f(n-1, w), // if we don’t put the nth item in the bag
f(n-1, w – w[n-1]) + v[n-1] // if we put the nth item in the bag
)

Well, I understand the phrase “the back of the envelope” as fast rough estimation / calculation that people can do on the back of en envelope…So this column is mainly about rough calculation / estimation…I’ll mark some of the points from the book here.

How much water flows out of the Mississippi river every day
This is the beginning question in this column. But if you look at the river as a big long cube, then the result = speed (meter/day) * depth (meter) * width (meter)

- One point here is to make sure that dimension-wise, the calculation is correct ( meter^3 / day ).
- The other point is we can look at the problem from different angles, like the rainfall is X m / day, and the ‘flat size’ of the river is Y m^2, then the result = X * Y. Because roughly speaking, the water that flows in should equal to that flows out.

Casting out nines
This is a trick (that I didn’t learn in my childhood but I should…) to quickly verify if the sum / difference / multiplex is correct or not. Like 2045 + 5331 = 7376.
2045: 2 + 0 + 4 + 5 (- 9) = 2
5331: 5 + 3 + 3 + 1 (- 9) = 3
7376: 7 + 3 + 7 + 6 (- 18) = 5
2 + 3 = 5.

Rule of 72
This is pretty useful. Basically it calculates m = n * (1 + x%)^y. If x * y = 72 then roughly m = 2n

Constants…Rule of thumb
- Well, roughly, 2^10 = 1,000 (K), 2^20 = 1,000,000 (M), 2^30 = 1,000,000,000 (G), etc
- PI second is a nano-century, which is 100 * 10^(-9) = 10^(-7) year => 1 year = PI * 10^7 second. OK let’s look at the dimensions: micro (-3), milli (-6), nano (-9), etc

Little’s Law
This is interesting, IT example here: suppose you have an online system, the incoming request rate is N requests / second, and it takes M seconds to process it in the system; so at one point on average there will be N * M requests that is in processing.

Another restaurant sample: assume you are waiting in line for a restaurant that can tolerant N people, and on average people eating there spend M hour in there; then the speed of entering that restaurant is N / M people / hour. So what you can do is look at how many people in the line are in front of you, then you can make a calculation how long do you need to wait…

Problems
- (This is from real life) One of my colleague has a program that has 600 threads, each thread sleeps for 50ms and then wakes up to do some IO (database ops) for 10ms, etc. So what is the active thread count at one point on average?
Answer: Applying little’s law – so the activation is 50 + 10 = 60 ms / activation, or 1/60 activation/ms; the living time is 10ms. So the average count is 600 * 1/60 * 10 = 100 threads.

- In what situation, hand over materials by postman on bicycle is faster than high-speed Internet?
Answer: Huge size of materials that can be put in a U-disk. Prove it with data (Internet speed, etc).

- The death rate in your city?
Answer: According to the little’s law, assuming city population is somewhat fixed at N, and on average people stay in the city (living…) spend 70 years, then the rate is N / 70…

So, another post without code…- -

Part I covers different aspects of programming. And Part II is going to focus on one area: performance. Column 6 is the first chapter and it gives a case where a certain program (movement simulation in gravitational situation) can be speed up by 400 times. This is achieved by optimizing at different levels: algorithm, data structure, code tuning, data structure tuning, hardware upgrading, etc. So as program or IT solution is multi-level thing, performance optimizations are multi-level too.