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
1
-
2$\begingroup$ You're asking this in the wrong place. Perhaps math.stackexchange $\endgroup$– Chris GodsilCommented Feb 12, 2012 at 17:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Feb 12, 2012 at 17:23
-
2$\begingroup$ 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. $\endgroup$ Commented Feb 12, 2012 at 22:56