Directed Acyclic Graph (DAG), directly embeds into dynamic programming....as from Vazirani's notes, the useful property of the DAG is that its nodes can be linearized (topologically). So if we process these nodes in the topological order we have sub-problems solved and the solution can be used for the next level. In the simple example of shortest path, we need (u1,v) , (u2,v) are the edges adjacent on the node v. To solve the shortest path problem we need the shortest path to u1, u2 to get the shortest path to v. The wonderful property of the DAG's is that if we start with the topological SOURCE (may be hypothetical by adding 0 weight edges), we are sure that we solved u1,u2 before solving v (if we process the nodes in topological order)
Longest monotonic subsequence in a given sequence, suppose the given sequence is '5,2,8,6,3,6,9,7' (The longest monotonically increasing sequence) in this is 2,3,6,9.
On the first look, it appears that it doesn't have sub-optimality inside it. In the sense take a subsequence '5,2,8' the longest monotonically increasing subsequence in this is is (5,8) or (2,8) but neither (5,8) and (2,8) is not in the overall longest monotonic subsequence, so the question is how dynamic programming works here??.....well people don't talk about the sub-optimality here......but still this can be solved by dynamic programming...
Let me restate the principle of optimality here...."If a optimization problem involves of sequences of decisions d1,d2,d3,d4...dn . The principle of suboptimality states that what ever decision you make initially the rest of the decisions should still optimize whats remaining after making decision d1...i.e would form a sequence of decisions to save a smaller optimization problem
Any way I wrote the following code segment , S[i] = length of the longest monotonic subseqence ending at index i, input is a array of integers A[i].
global_max_length=-INFINITY;
PATH[N];
for(i=0;i0;j--){
if(A[j] < A[i]){
if(S[j]+1 > S[i]){
S[i] = S[j]+1;
if(S[i] > global_max_length){
global_max_length = S[i];
PATH[N] = j;
}
PATH[i] = j;
}
}
}
}
void printSeqence(){
int j=N;
do{
print("%ld ",A[PATH[j]]);
j = PATH[j];
}while(j!=PATH[j])
}
global_max_length , returns the length of the longest monotonic increasing sequence, and also prints the sequence
Apart from this life has been very cold, man today was REALLY_ __FREEZING__ here, I have cold the damn cold, I cannot drink cool drinks, eat any cold stuff it sucks......Well , I'll be going to India soon meet swapna,chamu...just talked to chamu on the phone, hope to see her and swappy soon...............THE LIFE GOES ON ON ON...by the way the GYM is closed till 26th and its cold outside I cannot even jog its really HELL out here
With love
...............Vamsi...............