Writing a proof for an algorithm

Question

Hi guys i am trying to compare 2 algorithms and thought i may try and write a proof for them !!! (my maths sucks so hence the question)

Normally in our math lesson last year we would be given a question like

prove: (2r + 3) = n (n + 4)

then i would do the needed 4 stages and get the answer at the end

Where i am stuck is proving prims and Kruskals - how can i get these algorithms in to a form like the mathmatical one above so i can proceed to prove

note: i am not asking people to answer it for me - just help me get it in to a form where i can have a go myself

thanks

Answer 1

You don't give many details but there is a community of mathematicians (Mathematical Knowledge Management MKM) who have developed tools to support computer proofs of mathematics. See, for example:

http://imps.mcmaster.ca/

and the latest conference

http://www.orcca.on.ca/conferences/cicm09/mkm09/

Answer 2

From my maths classes at Uni I (vaguely) remember proving Prims and Kruskals algorithms - and you don't attack it by writing it in a mathematical form. Instead, you take proven theories for Graphs and combine them e.g. http://en.wikipedia.org/wiki/Prim%27s_algorithm#Proof_of_correctness to build the proof.

If your looking to prove the complexity, then simply by the working of the algorithm it's O(n^2). There are some optimisations for the special case where the graph is sparse which can reduce this to O(nlogn).

Answer 3

Where i am stuck is proving prims and Kruskals - how can i get these algorithms in to a form like the mathmatical one above so i can proceed to prove

I don't think you can directly. Instead, prove that both generate a MST, then prove that any two MST are equal ( or equivalent, since you can have more than one MST for some graphs ). If both algorithms generate MSTs which are shown to be equivalent, then the algorithms are equivalent.

Answer 4

Most of the times the proof depends on the problem you have in your hand. Simple argument can be suffice at times, at some other times you might need rigorous proof. I once used a corollary and proof of already proved theorem to justify my algorithm is right. But that is for a college project.