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.