23 reputation
7
bio website bitsteller.blogspot.com
location Germany
age 30
visits member for 1 year, 8 months
seen May 3 '13 at 7:09
I'm ashamed to confess that I edited this page just to get another bronze badge ...

Nov
22
awarded  Benefactor
Nov
22
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.
Nov
21
awarded  Teacher
Nov
16
revised How to prove that a dynamic programming algorithm is a monotonic function
added 95 characters in body
Nov
16
awarded  Scholar
Nov
16
accepted How to prove that a dynamic programming algorithm is a monotonic function
Nov
16
answered How to prove that a dynamic programming algorithm is a monotonic function
Nov
15
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!
Nov
15
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.
Nov
15
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.
Nov
15
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 ;)
Nov
14
awarded  Promoter
Nov
11
awarded  Editor
Nov
11
revised How to prove that a dynamic programming algorithm is a monotonic function
fixed some errors
Nov
11
awarded  Student
Nov
11
asked How to prove that a dynamic programming algorithm is a monotonic function
Nov
11
awarded  Autobiographer