Every year, I teach my students about using induction to prove that algorithms function as intended. My purpose, in instructing them, is to help them master the structure of the proof itself. I use simple algorithms for which we can do fairly easy inductive proofs. Here are a few examples:

Prove that arraySum will correctly compute the sum of all of the elements in arr.

public int arraySum(int[] arr){
    int k = 0;
    for (int g = 0; g < arr.length; g++)
        k = k + arr[g];
    return k;
}

Prove that this function will return $n^2$: Assume n is positive.

public int square(int n){
    int sum = 0;
    int count = 0;
    while (count < n){
        sum = sum + n;
        count = count + 1;
    }
    return sum;
}

As you can see, I am not aiming for complicated algorithms. What my students need (and what I need) is a good source for practice problems. I'd absolutely love it if they were already carefully solved (so that my students could independently study with them and check their own answers), but I could work with any source that simply has a series of pre-made reasonable practice problems.

Is there any such resource out there?

Any book on elementary number theory will likely have quite a few recurrences as examples and in the exercises of the early chapters. For example, the sum of the first n odd integers is $n^2$. As a recurrence this is just $n^2$ = $(n-1)^2$ + $2*n - 1$. Or possibly it will be shown as $a_n$ = $a_{n-1}$ + $2*n -1$, with $a_1$ = 1.

Some books on discrete math have many of these as well. Some even have these in summation form, rather than as recurrences.

Likewise the sum of the first n integers (start counting with 1) is $n(n+1)/2$.

From these recurrences or sums you can develop a program to give the students or have the students prove the relations and then develop the program themselves.

Even a web search for recurrence relation turns up some ideas.

A rather important sum (the geometric sum) is this: Let r be a real number and k a non-negative integer. If $r \neq 0$ then $\sum_{n=0}^k(r^n)$ = $(1 - r^{k+1})/(1-r)$.

Moreover, if $|r| < 1$ then as k increases this sum approaches 1 - r which leads to an infinite sum that is pretty comprehensible.

Also David Gries' The Science of Programming has interesting examples that he shows along with how to develop programs from pre and post conditions. The book has been mentioned in answers to other questions here also.

I'm using many examples involving trees (height of a tree, number of leaves, ...) or graphs (number of edges in a fully connected graph, ...). The advantage is that if I force students to draw the first three or four steps, they are usually capable of deriving the equation by themselves.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.