How to Think About Algorithms - Loop Invariants and Recursion

Author : Jeff Edmonds, Department of Computer Science & Engineering, York University
Publication Date : Fall 2006

This document was suggested by John Pinto

Document Excerpts:

These are a preliminary draft of notes to be used in a twelve week, third year algorithms course. The goal is to teach the students to think abstractly about algorithms and about the key algorithmic techniques used to develop them.

There are so many algorithms that the students must learn that some get overwhelmed. In order to facilitate their understanding, most textbooks cover the standard themes of iterative algorithms, recursion, greedy algorithms, and dynamic programming. However, generally once it comes to presenting the algorithms and their proofs of correctness, these concepts are hidden within optimized code and slick proofs. One goal of these notes is to present a uniform and clean way of thinking about algorithms. This is accomplished by focusing on the structure and proof of correctness of the "meta-algorithms" Iterative and Recursive and within these the meta-algorithms Greedy and Dynamic Programming. By learning these and their proofs of correctness most other algorithms follow easily. The challenge is that thinking about meta-algorithms requires a great deal of abstract thinking.

The goal is not to present completed algorithms in a nice clean package; but to go slowly through every step of the development. Many false starts have been added. The hope is that this will help students learn to develop algorithms on their own. The difference is a bit like the difference between studying carpentry by looking at houses and by looking at hammers.

Intended Audience:

The course assumes that the students have completed a first year programming course and have a general mathematical maturity. The first chapter covers much of the mathematics that will be needed for the course.

View/Download How to Think About Algorithms - Loop Invariants and Recursion