# Tag Info

8

I think induction should be taught first, and then loop invariants, since you usually need induction to prove that the loop invariant is really an invariant, and also because you need induction for other purposes than just proving that a loop invariant is really an invariant. In fact, in most curricula for Computer Science at university will have some math ...

6

Let's start with the term "Loop Invariance". It is a property of a loop that is true before and after each iteration, thus in-variant, non-changing. So then, what is the purpose of the loop invariance in proving algorithm correctness? That is, it is a predicate about what the loop is supposed to do. Thus with proof by induction on this predicate shows the ...

4

To give an explanation of this requires a problem in which to frame the discussion. I propose the Dutch National Flag problem, likely first proposed by Dijkstra, but I'm not positive. I'll pose the problem first and discuss the solution using invariants. The Problem Taken from The Science of Programming. You have an array of n elements. Each element ...

4

I have been teaching theoretical CS to math teachers (don't ask why...). I assumed that they were comfortable with numerical induction and therefore the transition to structural induction (on a computation as in proving invariants) wouldn't be difficult. I was wrong on both counts. It seemed to me that this is partly because they encountered induction in a ...

4

Since you are doing this in the context of code correctness, one incentive is to tell student that in some cases, you have to prove code, not test it. Anything critical (pick up your example, nuclear plant command system, plane autopilot, …) requires the highest level of confidence. Tests are always going to be partial. They will test 1, 10, 1000 possible ...

3

I try to introduce induction not only as method for proving an algorithm, but as a method for developing algorithms as well. The idea is from Introduction to Algorithms by Udi Manber. Sometimes the way of thinking solve the problem for n=1 think about how you can calculate (n+1) once you know n helps them to develop solutions on their own. And it helps ...

3

One big struggle is getting CS students to care about induction. Proving correctness doesn't really count as motivation, when "passing the tests" seems so much approachable and the extra benefits from proving correctness just don't seem worth the extra effort. On the other hand, if induction could be practically useful in designing algorithms in the first ...

3

Firstly, I believe that if the thought process is clear to you, then going through that process with your students, out loud, clearly and slowly, can help them understand what it is that you are trying to convey. Go through that process for a number of various examples, which show how you decide on a loop invariant in the varying situations (yes, that pun ...

2

A great resource for the instructor to learn the max about invariants is to go to the master. David Gries, The Science of Programming It isn't a book for novice learners, though. But understanding what is in this book will help you a lot in teaching programming via invariants. He reveals all. He and his son have an undergrad text book also, that might ...

2

At the CS1 level that I teach, I focus a lot on the role and the precise meaning of variables and encourage comments at the point of declaration that attempt to make these clear, especially variables that are involved in loops. Since the meaning of a variable changes as the loop body is executed, we "agree" to use the entry point as the standard point of ...

2

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 ...

1

This isn't really an answer, but I hope will provide a bit of insight for the OP into thinking about and presenting the problem. I think that recursion (in computing) and induction (in mathematics) are complementary, not identical ideas. The interplay between the two can give insight. In mathematical induction, we normally work outward from the base case....

1

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.

1

Do it in code, so that pupils can play with it. This code will throw an exception if the invariant is not met. Show how this can be useful in finding bugs in the program. The book a touch of class by Bertrand Meyer, is very good for teaching Object Oriented Programming and has examples (can't remember how many, but it is where I leant it). loop_example is ...

Only top voted, non community-wiki answers of a minimum length are eligible