## Exercises: Algorithm Correctness

May 142018Before attempting these exercises, you should read the posts on algorithm correctness, invariants and variants.

### Exercises

- In English, write down the preconditions (if any) and postconditions of the following simple algorithms:
- Write as many as possible of the preconditions and postconditions in 1. as assertions in Python.
- The algorithms below take integer inputs.
For each algorithm,
- Test enough inputs to discover the preconditions and postconditions, and write them as
`assert`

statements. - Write
`print(locals())`

before the loop and at the end of the loop body, to trace the execution. - Use your traces to find the loop invariant, and add
`assert`

statements to check it. - Use your traces to find the loop variant.

Algorithm B:`def algorithm_a(x, y): p = x q = y while q > 0: p += 1 q -= 1 return p`

Algorithm C:`def algorithm_b(x, y): p = x q = y while q > 0: p -= 1 q -= 1 return p`

`def algorithm_c(x, y): p = 0 i = 0 while i < y: p += x i += 1 return p`

- Test enough inputs to discover the preconditions and postconditions, and write them as

## There are no published comments.