 # DS&A

Data Structures and Algorithms ## Exercises: Algorithm Correctness

May 142018

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

### Exercises

1. In English, write down the preconditions (if any) and postconditions of the following simple algorithms:
2. Write as many as possible of the preconditions and postconditions in 1. as assertions in Python.
3. 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``````

## New comment

Your comment will not appear until a moderator approves it.

Atom

hosted on werp.site