3. Finding loop invariants

We now show you how to develop loop invariants. This calls for understanding the term "generalization", which is the topic of the first video.

The words generalization and generalize

Generalization is an important process in mathematics and compter science. Mathematicians often see a pattern on a few examples and generalize to a statement that they hope to prove true. We use generalization in finding loop invariants. This short video gives you a good idea what "generalize" means. You'll find out that it is easy. (3.1 minutes) Read it here: generalize.pdf

Generalizing by replacing a constant by a variable

We look at one way of generalizing a postcondition. This is an extremely useful method. We won't require you do perform this kind of generalization on new problems, but we will use it in presenting the development of some algorithms. (2.3 minutes) Read it here: replace constant by a variable.pdf

Generalizing by combining the pre- and post-condition of array diagrams

We will be presenting (the development of) several searching and sorting algorithms in the next few weeks. These are relatively easy, once you know how to find a loop invariant by generalizing two array diagrams. We show youthat here. (3.25 minutes) Read it here: generalize array diagrams.pdf