How to Think About Algorithms - Loop Invariants and Recursion

These notes teach the students to think abstractly about algorithms and about the key algorithmic techniques used to develop them.

Publication date: 01 Feb 2008

ISBN-10: n/a

ISBN-13: 9780521614108

Paperback: 454 pages

Views: 24,225

Type: N/A

Publisher: Cambridge University Press

License: n/a

Post time: 09 Oct 2006 03:24:04

How to Think About Algorithms - Loop Invariants and Recursion

These notes teach the students to think abstractly about algorithms and about the key algorithmic techniques used to develop them.
Tag(s): Algorithms and Data Structures Formal Methods
Publication date: 01 Feb 2008
ISBN-10: n/a
ISBN-13: 9780521614108
Paperback: 454 pages
Views: 24,225
Document Type: N/A
Publisher: Cambridge University Press
License: n/a
Post time: 09 Oct 2006 03:24:04
This book was suggested by John Pinto :)

From the Preface:

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.

About The Author(s)

Jeff Edmonds is a Professor and a member of The Theory of Computing Group, a part of the Department of Electrical Engineering and Computer Science at York University. His research interests are scheduling problems, lower bounds, randomness, and handling data.

Jeff Edmonds is a Professor and a member of The Theory of Computing Group, a part of the Department of Electrical Engineering and Computer Science at York University. His research interests are scheduling problems, lower bounds, randomness, and handling data.

Sponsors