Different types of Iterative Algorithms

Here are a few classic types of iterative algorithms to help you design a measure of progress and a loop invariant.

More of the Output:  if the solution is a structure composed of many pieces (e.g., an array of integers, a set, or a path), a natural thing to try is to construct the solution one piece at a time.

·      Measure of Progress:  The amount of the output constructed.

·      Loop Invariant: The output constructed so far is correct

More of the Input:  Suppose the input consists of n objects ( e.g., an array of n integers or a graph with n nodes). It would be reasonable for the algorithm to read them in one at time.

·      Measure of Progress:  The amount of the input considered.

·      Loop Invariant: Pretending that this prefix of the input is the entire input, I have a complete solution.

Narrowing the Search Space: If you are searching for something, try narrowing the search space, maybe decreasing it by one or, even better, cutting it in half.

·      Measure of Progress: the size of the space in which you have narrowed the search.

·      Loop Invariant: If the thing be searched for is anywhere, then it is in this narrowed sublist.

GCD LIKE: substitute the input with other instance much easier or smaller.

·      Measure of Progress: the new instance replacing the original input has smaller size or easier.

·      Loop Invariant:  if the new instance has been constructed whose solution is the same as the original instance, then I have the solution