For some background : I think I am quite good at advanced (graduate/research lev
ID: 650860 • Letter: F
Question
For some background : I think I am quite good at advanced (graduate/research level) mathematics and physics but I have no CS background. Now I am taking a graduate level class on algorithms.
I don't think I have ever written a wrong proof in mathematics - as in either I can prove something or I can't. I have never faced a situation whereby I wrote a wrong proof - its just obvious if I am writing a wrong proof.
BUT with algorithms it seems that its just trivial to write a wrong algorithm. I am simply not getting as to how does one know if what one has written is right or wrong. There seems to be something "mysterious" going on here - like while I write a recursive/dynamic programming solution etc. - I am thinking that I wrote something right but then somebody comes along with an example where my answer doesn't work!
Its quite contrary to my years of experience of writing proofs in mathematics!
This is getting freaking scary! Its better to not be able to do something than to be writing a wrong answer and not knowing it! (...often enough I land up writing a greedy solution trying to optimize something locally but its not the globally correct answer!..how does one see it!?...coming up with a counter-example is also almost always very hard!..)
Can someone help?
Explanation / Answer
You prove that the algorithm is correct. This requires (1) writing out a precise specification of what you mean by correctness, (2) writing a mathematical proof that your algorithm meets this specification. Algorithms courses and textbooks often include some material on how to prove algorithms correct, as well as many examples of this, so that would be a good starting point to study, if you want to learn more about proofs of correctness for algorithms. See also formal methods / formal verification, and possibly the following question on this site: How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect