Algorithms

This book confronts head-on the main challenges students face in algorithm design and analysis. While maintaining rigor, it breaks down some of the most difficult aspects of algorithm design into step-by-step procedures that all students can follow. In the discussion of basic algorithm design paradigms—graph search, reductions to solved problems, greedy algorithms, divide-and conquer, backtracking, dynamic programming, and gradient descent or hill-climbing—we emphasize not only the techniques themselves but also how to think when designing algorithms for new problems. The book also provides templates for correctness proofs that are tailored to each design paradigm. A wide range of examples are included for every paradigm, from canonical algorithms that clearly illustrate the core ideas to examples that stretch the paradigm in different ways. Within the existing toolbox developed by algorithms researchers, there are both standard tools that students should master and more surprising results that even their discoverers found remarkable. We present both, taking care to distinguish between them and to convey their different roles in algorithmic problem solving. The book includes many types of assignments designed to keep students engaged with the subject. Comprehension quizzes allow students to self-test their understanding of basic vocabulary and concepts. Algorithm design problems range from guided exercises, which walk students through the procedure for designing an algorithm, to open-ended problems that admit multiple correct approaches. Empirical experimental problems give students hands-on experience implementing algorithms (in a language of their choice), testing them experimentally, and summarizing collected data. These assignments also help students better understand both the significance and the limitations of asymptotic analysis, including the differences between worst-case, average-case, and typical algorithm performance. The book was developed for an upper-division undergraduate algorithms course, but it can also be used for a lower-division class (starting with the appendices) or an introductory graduate course (including the optional advanced sections).