Techniques for the design and analysis of algorithms are at the heart of computer science. They are essential for solving complex problems, understanding those that are hard to solve, and creating applications that are efficient in their use of both space and time. Algorithms: design techniques and analysis is an addition to many other excellent textbooks on this subject. It offers broad and deep coverage of the topics while avoiding implementation idiosyncrasies and mathematical details.

The book consists of seven parts. Part 1 provides the background information for the subsequent chapters. Fundamental algorithms for searching, merging, and sorting are used for explaining the mathematical concepts that underlie the analysis of algorithms. Basic data structures employed in the design of efficient algorithms are also investigated, with special treatment given to priority queues and disjoint sets. Part 2 focuses on recursive design techniques that lead to concise and easy-to-understand solutions to many complex problems. These techniques include induction, divide and conquer, and dynamic programming. Part 3 covers the greedy and graph traversal approaches for solving some well-known problems such as single-source shortest path, minimum cost spanning tree, and Huffman code. Part 4 covers NP-completeness and computational complexity, looking at a class of problems that are not known to be solvable in polynomial time. Part 5 covers techniques, such as backtracking, branch-and-bound, and randomization, for finding approximate solutions to these hard problems in a reasonable time. Part 6 focuses on two important problems--finding maximum flow in a network and finding maximum matching in an undirected graph--to demonstrate an algorithm design technique called iterative improvement. Part 7 uses geometric sweeping and Voronoi diagrams to solve a class of problems that are inherently geometric in nature.

The concepts, techniques, and algorithms in the book receive systematic treatment. Explanations of algorithmic techniques are followed by pseudocode representations of the algorithms; examples are used for illustrating their inner workings; and a concise analysis of space-time complexity is presented. The level of treatment given to the material requires only elementary knowledge of discrete mathematics and data structures. Appendices A and B and chapter 2 provide this prerequisite background.

This book is intended as a textbook. The first three parts of the book are well suited for an undergraduate course, whereas the rest could be taught as a graduate course in algorithm design and analysis. It will also be useful to programmers and software engineers who are looking to gain systematic and in-depth exposure to topics that are central to their practice.

More reviews about this item: Amazon