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**: 21,914

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.

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.

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.

Tweet

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.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Microsoft .NET
Rexx
Perl
PHP
Python
R
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors