ABSTRACT

Techniques for Designing and Analyzing Algorithms

Design and analysis of algorithms can be a difficult subject for students due to its sometimes-abstract nature and its use of a wide variety of mathematical tools. Here the author, an experienced and successful textbook writer, makes the subject as straightforward as possible in an up-to-date textbook incorporating various new developments appropriate for an introductory course.

This text presents the main techniques of algorithm design, namely, divide-and-conquer algorithms, greedy algorithms, dynamic programming algorithms, and backtracking. Graph algorithms are studied in detail, and a careful treatment of the theory of NP-completeness is presented.

In addition, the text includes useful introductory material on mathematical background including order notation, algorithm analysis and reductions, and basic data structures. This will serve as a useful review and reference for students who have covered this material in a previous course.

Features

  • The first three chapters provide a mathematical review, basic algorithm analysis, and data structures
  • Detailed pseudocode descriptions of the algorithms along with illustrative algorithms are included
  • Proofs of correctness of algorithms are included when appropriate
  • The book presents a suitable amount of mathematical rigor

After reading and understanding the material in this book, students will be able to apply the basic design principles to various real-world problems that they may encounter in their future professional careers.

chapter Chapter 1|36 pages

Introduction and Mathematical Background

chapter Chapter 2|30 pages

Algorithm Analysis and Reductions

chapter Chapter 3|38 pages

Data Structures

chapter Chapter 4|66 pages

Divide-and-Conquer Algorithms

chapter Chapter 5|44 pages

Greedy Algorithms

chapter Chapter 6|38 pages

Dynamic Programming Algorithms

chapter Chapter 7|76 pages

Graph Algorithms

chapter Chapter 8|38 pages

Backtracking Algorithms

chapter Chapter 9|52 pages

Intractability and Undecidability