Exercises: Algorithm Correctness
May 142018Before attempting these exercises, you should read the posts on algorithm correctness, invariants and variants.
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.