Proving Algorithm Correctness?

[ECEsasha]

Hi, I'm wondering if anyone could help me understand algorithm correctness. I've read the wiki page, along with lecture slides, but I have no idea how to apply it.

Explaining it on a simple program would be extremely helpful.


This is one simple example someone could explain with.

#include <iostream>
#include <cstdlib>

using namespace std;


int main(int argc, char** argv){

	int least = atoi(argv[1]);

	for(int index = 2; index < argc; index++){

		int next = atoi(argv[index]);

		if(next < least){
			least = next;
		}

	}


	return 0;
}

What I really want to know is if someone asks me to "prove the algorithm's correctness", what exactly would I do?


Any helpful links could possibly help immensely, too!

[ECEsasha]

Anyone? D:

[Cody0023]

Algorithm correctness is stating does this algorithm do what I want it to do? And if it does you have to prove it. Just like proofs in geometry.

It seems in your program you are trying to find the smallest element? If thats the case the question is how the hell did you do that?

http://www.cs.loyola.edu/~lawrie/CS295/F08/lectures/295-8.pdf

[JLBorges]

See: http://cs.engr.uky.edu/~lewis/essays/algorithms/correct/correct1.html

Beware of bugs in the above code; I have only proved it correct, not tried it. - Donald Knuth (1977)

[ECEsasha]

Thanks!
These are helpful guidelines :D

Haha, nice quote.