Dynamic Programming Notes

October 15th, 2009

1. DP on Sequence

(1) Simple Induction
Formula: f(i) = g(f(i-1), w(i))
Examples: Assembly-line Scheduling (CLRS), mean filter, …

(2) Sequential Division(# of divisions unknown)
Classic Problem: LDS
Formula: f(i)=optimize{f(k)+w(k+1,i)}
where f[i] is the optimum value for s[0..i]
Extension: Sort the sequence first and then do LDS. We may need to sort the sequence using multiple keywords and then do LDS on the last keyword in the cases where one keyword is equal..
Examples: Beautiful People (sgu199), segments (ural 1078), Printing Neatly(CLRS)

(3) Sequential Division(# of divisions known)
Formula: f(i,j)=optimize{f(k,j-1)+w(k+1,i)}
where f(i,j) is the optimal division of s[0..i] into j parts.
Examples: Integer Multiplaction(given n digits, add m multiplication signs to achieve maximum product)

(4) Hierachical Division
Formula: f(i,j)=optimize{f(i,k-1)+f(k+1,j)+w(i,j,k)}
where f(i,j) is the sum of weights associated with the optimal division of s[i..j].
Examples: Matrices Multiplication, Optimal Binary Search Tree, Triangulation of Simple Polygon

(5) Hierachical Division (on Looped Sequence)
Formula: f(i,j)=optimize{f(i,k)+f(t,j-k)+w(i,j,k)}
where t=(i+k)mod n. Let j’=(i+j)mod n, then f(i,j) is the sum of weights associated with the optimal division of s[i..j’] (i.e. j consecutive elements from s[i]). w[i,j,k] is the weight for dividing s[i..j’] at t.
Examples: Pebble Merging

(6) Matching Two Sequences
Classic Problem: LCS
Formula:
f(i,j) = optimize{ f(i-1, j-1) + w(i,j),
                           f(i   , j-1) + w(empty,j),
                           f(i-1, j   ) + w(i,empty)}
where f(i,j) is the best soultion for x[0..i] and y[0..j]. Pre-conditions may be associated with the tree terms to be optimized.
Examples: Little Shop of Flowers(sgu104), Editing Distance(CLRS)

2. DP on trees/graphs

No special formula. Use post-order DFS on trees and optimize over all children. DP for trees are typically in O(n).
Prim/Kruskal, Dijkstra are typical DP on graphs.

3. DP for NP problems

Basic Problems: 0-1 Knapsack, Weighted Scheduling, Scheduling to Maximum Profit(CLRS)
Formula: f(i,j)=optimize{f(i-1,j),f(i-1,j-c(i))+w(i)}
where f(i,j) is the optimum value for x[0..i] under the constraint of j resources, c(i) is the cost of i, w(i) is the gained weight of i.
Tips: You only have two choice for each i, pick it or leave it there.

Experience Your Life

October 5th, 2009

Recently I’m thinking about what kind of life I would like to lead – a plain but carefree life, or one with chanllenges and uncertainties. This leads to a philosophical problem of the goal of our life. I partially agree with some people who hold the idea that we live to pursue happiness. After all, people earn money, run after fame and authority, in order to get some self-satisfaction – that is, to be happy with themselves. However, I don’t think happiness is all the story.

Consider people who take the roller coaster. Do they only want to pursue happiness? Not so much as they pursue excitement, or, kind of, fear. Then consider people who take some adventures. Do they only want to pursue the greater happiness after they succeed? Perhaps not. They are enjoying the uncertainty in the challenge itself. Even when it comes to people who own fame and authority, it cannot be said that they are more happy than others – they are bound to lose some of their privacy and to have more things to worry about than others. But their lives are just more colorful than others. Why?

Here goes the answer – we live to experience. Not to be happy, nor to be afraid, but to experience. No matter happiness or pain, delight or sorrow, courage or fear, they are just part of our experience on our life journey. The longevity of a person should not be based on how many years they are alive, but on how much they experience – either happy or not. Consider a vegetative patient, he does not live as long as his heart bumps because he experience nothing while he’s asleep. Life is to experience. This is why I’m strongly against the idea of euthanasia – it deprives the person of the right to experience, whether he is willing to do so or not.

The famous legends writer, Jin Yong, once said in his book "The Legend of Condor Hero", "Big ups and downs are better than no ups and downs; Great joy and sorrow are better than no joy and sorrow". The meaning of life lies in experience. So I will choose to lead a life that is unique, that is full of uncertainty but of surprise at the same time. I am willing to experience anything on my way of the big adventure!

Not best, but optimum

October 5th, 2009

I’m born a sentimental people. More often than not, I’ll think of my past and sigh for the lost. I’ve lost the admission to my ideal college; I’ve lost the chance to take part in a world-famous algorithm competition; I’ve lost some much, much more important things better left unsaid here.

Scraps of memory make me painful, frustrations let me down, and then failures become excuses for my laziness. When ideal goals are no longer achievable, why work hard? Every time I’m about to give up as such, something will well up from my deep heart.

Just a month before the college entrance examination, a psychologist was invited to give us a lecture on preparing for the exam. He told us that he could not deny that the exam was a rather important one, which might, to some degree, determine our future development. But there were some crucial rules that one should always keep in mind. “You may not have the chance to choose the best, but you are always welcome to make the optimum.” He wound up his speech with these words. And these words, I treasure.

Yes. Everyone has his ideal. But not every dream can come true. When a dream shatters, I have to reconcile. I have to reconcile because there is no other choice. This reconciliation makes me painful, yet makes me grow. Past has passed. I’ve got better things to do than dwell upon the past. When best is no longer achievable, my focus should be on the optimum. Of course, optimum bears no comparison with best; but the former is still realizable. Attempting something unrealizable is like living in the fantasy; grasping the chances still available is the only rational choice.

But even this optimum is not something I can take in my stride. I’ve to pay a lot though the outcome is unpredictable. I’ve to work hard when others are resting, to refrain myself from entertainment when everybody is amusing themselves. Sometimes I may gain less than those who don’t pay so much. And the discouraging results may make me slack at my work for a while. But I have to revive as soon as possible, because I know while endeavor doesn’t ensure optimum, slack means total failure. I may be exhausted, but I shall never be overwhelmed.

The retrospect is always depressing and the future is yet to come. I’ll never have the right to retrieve the best, but I can always strive for the optimum!

CUDA + VS2008

October 3rd, 2009

My Environments:

Windows 7 Professional, VS2008 + VAssistx 10.5.1738.0,

ATI X1400 Graphics Card (No need of NVidia GC if you only want to run the program as emulation, great news!)

Steps:

1. Install Visual Studio, then CUDA Toolbox 2.3, then CUDA SDK 2.3

2. Follow the link to configure.

3. Download Cuda Wizzard (a project template) here and setup

4. Create a new CUDA project(after you install the wizzard, there should be a CUDAWinApp template)

5. Switch from “Debug” to “EmuDebug” or “EmuRelease” (IMPORTANT!) This allows you to simulate your program on your CPU rathen than CG. Even if you have NV CG, you should still do this if you want to debug (set breakpoints, etc.)

6. Enjoy!

This does not work on VS2010.

Hello, World!

September 28th, 2009

It’s great fun to have this new blog site set up and use Live Writer to post a blog. Hmm… I’ll try to integrate this blog into by personal website when I am free.

BTW, is there a time I would be free? :)