DS&A - Data Structures & Algorithms - Exercises: Algorithm Correctness

Exercises: Algorithm Correctness

May 142018

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

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 A:
```
def algorithm_a(x, y):
    p = x
    q = y
    while q > 0:
        p += 1
        q -= 1
    return p
```
Algorithm B:
```
def algorithm_b(x, y):
    p = x
    q = y
    while q > 0:
        p -= 1
        q -= 1
    return p
```
Algorithm C:
```
def algorithm_c(x, y):
    p = 0
    i = 0
    while i < y:
        p += x
        i += 1
    return p
```