Exercises: Algorithm Correctness
May 142018Before attempting these exercises, you should read the posts on algorithm correctness, invariants and variants.
Variants
May 142018An algorithm is correct if it always returns the correct result.
Assertions are our main tool for proving algorithms are correct; they state that some condition will be true whenever a particular line of code is reached. The goal is to assert that, when the algorithm finishes running, the result is correct. If this assertion never fails, then the algorithm will never return a wrong result.
Invariants
May 142018An assertion is a claim about the state of a running program — it says that some logical condition should be true whenever a particular line of code is reached. In the previous post, we only considered assertions in code where each line is executed once, in sequence.
Of course, real algorithms are more complicated, because loops and recursion cause some code to be executed multiple times, not in a simple sequence. In this post we’ll explore invariants, which are needed to prove correctness of non-trivial algorithms.
Is Your Algorithm Correct?
May 142018When we write an algorithm to solve a problem, the algorithm is only correct if it does actually solve that problem. That should be obvious! But how do we know whether an algorithm is correct?
This is a genuine concern because algorithms often aren’t correct, and we need to debug them. We need a way to analyse an algorithm to decide if it really does solve the problem or not.