Algorithms and correctness

Algorithmic problem

An algorithmic problem is described by:

1. a set of feasible inputs.
2. for each input a set of feasible outputs;
3. optionally, an objective function, which assigns a real number to each feasible solution (the quality of the feasible solution). If an objective function is specified, it is also specified whether the objective function is to be minimized or to be maximized.

Operations and instructions

A programming languages offers a possibility to specify instructions (a.k.a. statements). An instruction specifies a sequence of operations; executing the machine amounts to executing this sequence of operations.

Algorithm

1. An algorithm is associated with an algorithmic problem.
2. An algorithm is a sequence of instructions how to compute a feasible output for a given input.
3. If an objective function is given, the objective function value of the generated solution is a criterion for the quality of an algorithm. More specifically:
   1. in case of minimization: a low objective function value is favored;
   2. in case of maximization: a high objective function value is favored.

Iterative and recursive algorithms

1. Basically, a non-trivial algorithm is a loop or recursion plus some preprocessing and/or postprocessing.
2. If an algorithm consists of several loops/recursions that are

nested loops/recursions

Correctness

An algorithm is correct if three conditions are fulfilled for every feasible input:

1. All operations are well-defined. For example, access to an array component outside the array's index range and
2. Each loop and recursion terminates regularly, that is, the break condition is fulfilled after a finite number of operations.
3. The output delivered by the algorithm is a feasible output for the given input.

Invariant

1. The invariant of a loop is a set of statements, which are fulfilled immediately before the first iteration, immediately after the last iteration, and between two iterations.
2. The invariant of a recursion is a set of statements, which are fulfilled immediately after
3. after preprocessing Maintenance of the

Remarks:

1. The invariant has a specific function in the correctness proof for the algorithm. It should contain all statements relevant for this purpose. It should contain no further statements unless there is a good reason for that.
2. Important for tests!

Variant

Remarks:

1. The invariant has a specific function in the correctness proof for the algorithm. It should contain all statements relevant for this purpose. It should contain no further statements unless there is a good reason for that.
2. Important for tests

Correctness proofs

1. The variant must be specified in a way that allows to conclude that the break condition will be fulfilled after a finite number of iterations.
2. The invariant

'Remark: for complexity the number of iterations bounded.