The most important change in this edition is the new order of the chapters on decrease-and-conquer and divide-and-conquer. There are several advantages in introducing decrease-and-conquer before divide-and-conquer:
- Decrease-and-conquer is a simpler strategy than divide-and-conquer.
- Decrease-and-conquer is applicable to more problems than divide-and-conquer.
- The new order makes it possible to discuss insertion sort before mergesort and quicksort.
The idea of array partitioning is now introduced in conjunction with the selection problem. The author took advantage of an opportunity to do this via the one-directional scan employed by Lomuto’s algorithm, leaving the two-directional scan used by Hoare’s partitioning to a later discussion in conjunction with quicksort.
Binary search is now considered in the section devoted to decrease-by-aconstant-factor algorithms, where it belongs.
The second important change is restructuring of Chapter 8 on dynamic programming. Specifically:
- The introductory section is completely new. It contains three basic examples that provide a much better introduction to this important technique than computing a binomial coefficient, the example used in the first two editions.
- All the exercises for Section 8.1 are new as well; they include well-known applications not available in the previous editions.
- The author also changed the order of the other sections in this chapter to get a smoother progression from the simpler applications to the more advanced ones.
More applications of the algorithms discussed are included.
The section on the graph-traversal algorithms is moved from the decrease-and-conquer chapter to the brute-force and exhaustive-search chapter.
The Gray code algorithm is added to the section dealing with algorithms for generating combinatorial objects.
The divide-and-conquer algorithm for the closest-pair problem is discussed in more detail.
Updates include the section on algorithm visualization, approximation algorithms for the traveling salesman problem, and the bibliography.
The author added about 70 new problems to the exercises. Some of them are algorithmic puzzles and questions asked during job interviews.

Shop for university

Log into digital learning platforms

Subject catalogue

Get support

Support

Digital learning platforms

Resources by discipline

Get support

Support

Get inspired

Key series

Shop by category

Support

Support

Support

Subject catalogue

Shop for university

Log into digital learning platforms

Get support

Resources by discipline

Digital learning platforms

Get support

Shop by category

Get inspired

Key series

Introduction to the Design and Analysis of Algorithms, International Edition, 3rd edition

Shopping

Explore

Help & support

Pearson