Writing a proof for an algorithm [closed]

Question

I am trying to compare 2 algorithms. I thought I may try and write a proof for them. (My math sucks, so hence the question.)

Normally in our math lesson last year we would be given a question like <can't use symbols in here so left them out>.

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.

Answer 1

To prove the correctness of an algorithm, you typically have to show (a) that it terminates and (b) that its output satisfies the specification of what you're trying to do. These two proofs will be rather different from the algebraic proofs you mention in your question. The key concept you need is mathematical induction. (It's recursion for proofs.)

Let's take quicksort as an example.

To prove that quicksort always terminates, you would first show that it terminates for input of length 1. (This is trivially true.) Then show that if it terminates for input of length up to n, then it will terminate for input of length n+1. Thanks to induction, this is sufficient to prove that the algorithm terminates for all input.

To prove that quicksort is correct, you must convert the specification of comparison sorting to precise mathematical language. We want the output to be a permutation of the input such that if i ≤ j then a_i ≤ a_j. Proving that the output of quicksort is a permutation of the input is easy, since it starts with the input and just swaps elements. Proving the second property is a little trickier, but again you can use induction.