Chapter 1.3 of Algorithm Design Manual (Skiena) - “Reasoning About Correctness”

  • Show correctness through proofs
  • We should try to show both correctness and not incorrectness

MIT 6.006 L1 - Introduction provides some tips on showing correctness

  • For small inputs, we can use case analysis
  • For large inputs, algorithm must be recursive or loop in some way

Incorrectness

  • A good way to demonstrate incorrectness is through counterexamples
    • Think small – counterexamples are often present in simple cases
    • This exhaustively – there are usually only a small number of possible instances for the first non-trivial value n when it comes to algorithms
    • Hunt for weakness – if the proposed algorithm is of the form “always take the biggest” (greedy algorithm), think about why this might be the wrong thing to do
    • Go for a tie – break greedy heuristics by providing instances where everything is the same size
    • Seek extremes – usually easy to reason about