-1

Hello,

Thanks in advance for answering my questions :)

The question is: What do we mean by "Proving an algorithm"?

I'm having a problem in where to start (if I want to use contradiction for example)...

Thanks again Abdallah

flag
1 
 You're asking this in the wrong place. Perhaps math.stackexchange – Chris Godsil Feb 12 2012 at 17:21

closed as off topic by Andy Putman, Zev Chonoles, Felipe Voloch, Chris Godsil, quid Feb 12 2012 at 17:25

1 Answer

1

It means to prove

  • that the algorithm terminates
  • that the answer given by the algorithm is correct

It is/seems sometimes obvious, but in general it isn’t.

link|flag
2 
 I agree with this answer in the case of more-or-less traditional algorithms, computing some function, which is almost surely what the OP meant. Nevertheless, it might be worthwhile to mention that other notions of proof are appropriate for other sorts of algorithms. For example, if the algorithm uses randomization, you might want to prove reasonable lower bounds for the probability of termination and/or correctness. If the "algorithm" is an operating system, you might want to prove that it doesn't terminate. – Andreas Blass Feb 12 2012 at 22:56

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