Algorithms: A Gentler Approach

Author(s): Russell Impagliazzo and Ragesh Jaiswal

This book confronts the main challenges students have with algorithm design and analysis head-on. While maintaining rigor, we break down some of the most difficult aspects of algorithm design into step-by-step procedures that average students can follow. Included in the discussion of the basic algorithm paradigms (graph search, reductions to solved problems, greedy algorithms, divide-and-conquer, backtracking, dynamic programming, gradient descent/hill-climbing) are discussions of how to think when designing such algorithms for new problems. We also give templates for correctness proofs tailored to the specific algorithm design paradigms. A variety of examples of algorithms using each paradigm are given, ranging from the canonical algorithms following that paradigm to examples that stretch the paradigm in different ways. In the existing toolbox developed by algorithms researchers, there are both standard tools that students should be able to master and miraculous gems that surprised even their discoverers. We present both, being careful to distinguish the two.

We include many types of assignments meant to keep students engaged with the subject. Comprehension quizzes are meant for students to self-test their understanding of the basic vocabulary and ideas being presented. Algorithm design problems range from guided problems, which walk the students through the procedure for designing an algorithm, to open-ended problems with a variety of correct approaches. Empirical experimental problems give students hands-on experience with implementing algorithms (in the language of their choice), testing them experimentally, and providing summaries of the collected data. They are also meant to give students a better sense of both the significance and limitations of asymptotic analysis, with a clearer understanding of the differences between worst-case, average-case, and typical performance of algorithms.

This book was developed for an upper-division undergraduate algorithms class. However, it could also be used for a lower-division class (starting with the appendices), or an introductory graduate class (including the optional advanced sections).

< Back to Titles in Development List