More on Amortization

HouseBuyingTips.com - How to Buy a House

Automatic Code Instrumentation is an interesting article that describes a way to instrument code written in VC 6.0. It relies on the __penter() function to do the trick. Recompilation is required.

Dentist

It is ridiculously difficult to find a good dentist. I have been spending the whole afternoon searching on the Internet and calling around, but they all look the same to me. I have no idea how good they are! Worse, this is not like other services where failed comparison shopping only means the waste of some time and money, a bad dentist or doctor can affect one's body and health.

Notes on Dynamic Programming

I have been reading about dynamic programming these days. At least to me, dynamic programming appears to be more of a problem solving methodology than a computer programming technique. It is especially effective for certain optimization problems or matching problems, and usually it results in strikingly simple code.

Steps to Design a Dynamic Programming Algorithm

• Design a recurrence that breaks the problem down. (See note below)
• Compute the boundaries.
• Compute the recurrence in such a way that it only refers to values already computed.

Notes on the art of designing a recurrence

Perhaps the most difficult step of dynamic programming is to work out a proper recurrence relationship. In part, I believe that recurrence relationships are problem specific, and the designing or discovering of it is really art. In part, I do find that the form of the recurrence relationship is somewhat correlated with the nature of the problem. In the following section, I attempt to categorize the problems and study the form of the recurrence.

"Linear" Problems vs. Nested Problems

"Linear" problem can be divided into several smaller problems that do not nest each other. The string matching problem is linear because one match between the two strings does not nest other matches. The linear partitioning problem and the largest sum of a run problem are other examples of linear problems.

The solution of such a problem usually has the form S=S1+S2+S3+...+Sn, where Si are partial solutions. Similarly, the cost function of linear problems can often be described as the sum of the cost of a single step and the cost of the rest of the problem.

T(i)=T(i-1,j)+C(j)

A nested problem can be divided into two or more similar sub-problems, each of which can be further divided into sub-problems. Matrix multiplication problem is a typical nested problem. It involves adding parentheses to modify the order of multiplication, and parentheses nest.

The solution of such a problem can typically can be described as a tree that describes the nested relationship of the partial solutions. Similarly, the recurrence relationship can typically be described in the following form:

T(i,j)=T(j,k)+T(k,j)+C(k)

Ordered vs. Non-ordered Problem

Some problems have implicit orders. It is only possible to match sub-strings in the order of their occurrence. Similarly, it is not possible for matrices to exchange places in the matrix multiplication problem. Some problems do not have orders. You can choose any city as your next step in the TSP problem.

For ordered problems, it is usually possible to use only the position of the sequence to describe the partial solutions; for non-ordered problems, however, you will have to use sets to do so. This difference has severe difference in the time complexity of the generated algorithm.