3
$\begingroup$

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?

I am currently doing a lot of practice with this but I wonder if there is something that I am missing totally!

$\endgroup$
4
  • $\begingroup$ Proving algorithms correct usually requires an inductive proof. This is certainly true of dynamic programming algorithms. Greedy algorithms can generally be proved (assuming they are correct) by contradiction. Of course, here is the problem of "finding a counterexample". If you do not find the/a counterexample (if one exists) when doing your proof by contradiction, you will erroneously state that your proof is correct. $\endgroup$
    – Jared
    Oct 17, 2014 at 5:43
  • 3
    $\begingroup$ You say that you've never written an incorrect proof in mathematics and then immediately give an example of an incorrect proof that somehow doesn't count because you're calling it "computer science" rather than "mathematics". Assuming that reaching a local optimum implies you're at a global optimum is just the sort of thing that causes flawed proofs in general mathematics, too. Honestly, it's completely implausible that you've never written an incorrect proof, and would be even without the example you quote. Everybody makes mistakes; sometimes, they're subtle and hard to spot. $\endgroup$
    – David Richerby
    Oct 17, 2014 at 12:13
  • $\begingroup$ Here's a comforting thought: it's far more likely that you've written lots of incorrect proofs in mathematics, and simply never had anyone catch your mistakes. In seriousness, you can write correctness proofs for algorithms or - better yet - for complicated problems, look up correct algorithms. $\endgroup$
    – Patrick87
    Oct 17, 2014 at 15:18
  • $\begingroup$ I don't think I will write an incorrect proof and not know it. But it looks very easy to write a wrong algorithm and not be able to see that it is wrong! This is the queer thing. Somehow algorithm seems to need some sort of a "looking into the future" - about what all can happen... $\endgroup$
    – guest
    Oct 18, 2014 at 2:04

2 Answers 2

Reset to default
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ well - the issue I think is different - given a correct algorithm, trying to come up with a proof of corectness is I think not what I am asking for - I am looking for a way to know if I am writing a wrong algorithm in the first place! Algorithm writing somehow seems to need some sort of a future thinking - whereby I need to know ahead of time all that can happen - at any intermediate step I really don't know if I am doing it right or not! $\endgroup$
    – guest
    Oct 18, 2014 at 0:44
1
$\begingroup$

That's a great question, and the answer has nothing to do with coding. The answer is simple: in order to prove that an algorithm is correct, you will have to... hmmm... prove it!

An algorithm, in many senses is an abstract mathematical creature, which you can mathematically verify under certain assumption and conditions. Maybe the confusing part is that Algorithm can be CODED into a program, but this is only an instantiation of the algorithm, not the algorithm itself. It might be easier to keep the algorithm as a "pseudo code" to be able to define its supposed action, without the disguising details of the specific programing language you use. That way it is easier to believe that an algorithm is indeed a mathematical object (which is run on a mathematical abstraction of a computing device, e.g. on a Turing machine).

Given an algorithm $\textsf{ALG}$ that is supposed to do $X$, you can consider the (mathematical!) theorem "$\textsf{ALG}$ does X" and then try to prove it. To be concrete: assume you write a sorting algorithm $\textsf{SORT}$, then to prove it correct you want to prove the theorem "on input any list of $n$ numbers, $\textsf{SORT}$ outputs a lexicographical ordering of the input"

The details of proving such a theorem vary according to your algorithm and the problem you wish to solve. It's too broad to discuss in this thread.

However, to get some intuition, I would recommend you to look at graph-theory and algorithms for graph-theory. There are many nice algorithms for various graph-related tasks (e.g., performing a BFS search, doing a DFS search, finding a spanning tree, etc) and you will be able to find detailed proofs that those algorithms actually work they way that should (e.g., that BFS covers all the nodes and in the right order; that the spanning tree is indeed a spanning tree, etc.). Since the field of graph-theory is very close to mathematics, these examples might help you to "bridge" you prior knowledge and apply it onto computer-science questions.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.