Lecture Notes for Algorithm Design

Algorithms and States, 23 November 1999

1. a variable represents a value

   1. the state of a variable is given by the variable's value

   2. characterizations about a variable's state are presented as characterizations about its value

      1. the variable x is positive

      2. the (value of the) variable x is between 1 and 5

   3. variable state characterizations can be abstract

      1. the (value of the) variable x is an integer

      2. the (value of the) variable x is undefined

   4. it is easy to confuse a variable's value with its state

      1. variable state represents many values

      2. variable value represents a single entity

      3. a variable's state may or may not be true at any particular time

      4. confusing the two at this level is not dangerous, but should be avoided

2. an algorithm is a collection of variables (among other things)

   1. the state of an algorithm is the state of its variables

      1. not all variables need make up an algorithm's state

   2. two important algorithm states are the initial state and the final state

      1. the initial state describes what is true before the algorithm starts executing

      2. the final state describes what is true after the algorithm finishes executing

      3. the initial state is conserned with input variables; the final state is conserned with output variables

      4. the initial state is the precondition; the final state is the post condition

      5. example - swap(x, y)

         1. initial state - x = X and y = Y

         2. final state - x = Y and y = X

      6. example - square root

         1. initial state - x = X

         2. final state - x = sqrt(X)

         3. does this work always - no, not for integer x

   3. strong and weak states

      1. the description of a variable's state may represent several values - e.g. the value of the variable x is positive

      2. the more values a state description represents, the weaker that state description is - e.g. the value of x is greater than 5 vs. the value of x is positive

         1. a weak state description is less restrictive, it allows more values

      3. the fewer values a state description represents, the stronger that state description is - e.g. the value of x is an integer vs. the value of x is positive

         1. a strong state description is more restrictive, it allows fewer values

      4. one of the main stratagies for manipulating state descriptions is to strengthen them - that is, make them more restrictive - and to weaken them - that is, to make them less restrictive

         1. the choice between strengthening and weakening is sometimes a matter of taste and sometimes a matter of good policy

      5. example - square root again

         1. initial state - x = X is too weak; it admits too many values, some of which may not have a solution

         2. how to strengthen the initial state - x = X²

         3. now the post condition is x = X

         4. is this correct - traditionally, no because X could be negative; the initial state is still too weak

   4. the intial and final states are a functional specification for the algorithm

      1. an algorithm that begins when the initial state is true should end with the final state being true too

      2. if the initial state is false, what the algorithm does is undefined

      3. as a matter of good policy - initial states should be weak and final states should be strong

      4. a functional specification clarifies what needs to be done, and makes sure it's possible to do what needs to be done

      5. example - sorting

      6. initial state - a = A

      7. final state a = A' and A' = permutation(A) and for all i, j such that 0 <= i <= j < |a|, a[i] <= a[j]

This page last modified on 3 December 1999.