das_weezul
Reputation
Top tag
Next privilege 50 Rep.
Comment everywhere
 Nov22 awarded Benefactor Nov22 comment How to prove that a dynamic programming algorithm is a monotonic function Sorry for awarding the bounty so late. I thought you get the points automatically when I accept your answer. Nov21 awarded Teacher Nov16 revised How to prove that a dynamic programming algorithm is a monotonic function added 95 characters in body Nov16 awarded Scholar Nov16 accepted How to prove that a dynamic programming algorithm is a monotonic function Nov16 answered How to prove that a dynamic programming algorithm is a monotonic function Nov15 comment How to prove that a dynamic programming algorithm is a monotonic function By the way, thanks for sticking with me ;) I really appreciate your help! Nov15 comment How to prove that a dynamic programming algorithm is a monotonic function @user1151 You got me wrong. Let's say $MATCH(m-1,n-1) = 2$, $sim(a_m,b_n) = -1$, and the other cases are like you stated them. Then $MATCH(m-1,n-1)+sim(a_m,b_n) = 1$ and $max(1,0,0) = 1$ and therefore we found a counterexample because that means $MATCH(m-1,n-1) \gt MATCH(m,n)$. Again, by thinking through the recursion bottom up, I know that this can never happen, but I just cannot show it using my formula. Nov15 comment How to prove that a dynamic programming algorithm is a monotonic function Yes, that is the definition, but what is still bugging me is that in the case of $MATCH(m-1,n-1) + sim(a_m,b_n)$ the expression $sim(a_m,b_n)$ could be negative, but the whole expression could still be greater than the other options. In this case it could be that $MATCH(m,n) \lt MATCH(m-1,n-1)$. I mean that will never be the case, but I don't know how to prove that. Nov15 comment How to prove that a dynamic programming algorithm is a monotonic function I agree, by looking at the function, one concludes that the progression ought to be monotonic. But by writing $MATCH(m,n) \leq MATCH(m,n-1)$ you have not proved yet why $MATCH(m,n-1)$ must be smaller or equal than $MATCH(m,n)$. Or am I missing something? I'm really not that experienced when it comes to proofs, so bear with me ;) Nov14 awarded Promoter Nov11 awarded Editor Nov11 revised How to prove that a dynamic programming algorithm is a monotonic function fixed some errors Nov11 awarded Student Nov11 asked How to prove that a dynamic programming algorithm is a monotonic function Nov11 awarded Autobiographer