CMPUT 272 Required reading Variants and Invariants

Almost every algorithm repeats (iterates, loops) a certain transformation on a state of “things”; in other words, some task is repeatedly performed. There is a defined starting, initial state and an iterative algorithm defines a sequence of states. The next state in the sequence is obtained by a transformation of a previous state according to the algorithm. Such iterative processes are typically programmed using loops or using recursion. When studying iterative algorithms we look at the following issues (cf. [4]): • Does the algorithm stop? • Can a desired state be reached? • Does the algorithm reach (converge to) a state which does not change? • What are the reachable states? The principal strategy for answering such questions consists of finding what changes (a variant) when a transformation is performed and what stays the same (an invariant). Variant is a non-negative integer expression whose value decreases with each loop execu-tion. Variants are used to demonstrate the termination of an iterative process. Invariant is a relationship among elements of the state of an iterative process which holds on as long as the process is executed. Invariants are used for proving what the process does. Finding useful variants and invariants is a skill which is best learned by examples and we proceed to study several of them. Most of the material presented here is folklore but we try to give references to available sources