Ebook: 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:

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.

Here is a summary of the material covered in the book:

• Chapter 1 presents various mathematical topics, such as order notation, relevant mathematical formulae, probability theory and random variables.
• Chapter 2 examines various algorithm analysis techniques, including loop analysis. We also introduce reductions, which are revisited again in Chapter 9. Finally, we provide some examples of exact analysis in this chapter.
• Chapter 3 discusses various basic concepts in data structures, including stacks, queues, priority queues, binary search trees and hash tables.
• Chapter 4 treats divide-and-conquer algorithms. This chapter also contains a fairly detailed discussion of recurrence relations.
• Chapter 5 is a presentation of various greedy algorithms.
• Chapter 6 covers dynamic programming and memoization.
• Chapter 7 describes various graph algorithms, including breadth-first and depth-first search, minimum spanning trees and shortest path algorithms.
• The topic of Chapter 8 is backtracking algorithms, including pruning techniques and branch-and-bound. This is a topic that is not often found in textbooks on the design and analysis of algorithms.
• Chapter 9 presents the basic theory of NP-completeness, including the complexity classes P and NP, and NP-hard problems. Approximation algorithms are introduced and we also give a brief treatment of undecidability.

There are many textbooks on algorithms that contain more than 1000 pages of material. I have deliberately written a shorter book in which I have attempted to treat the essential concepts of the subject, by choosing a representative sample of useful algorithms to illustrate the most important design techniques. I have been careful to provide detailed pseudocode descriptions of the algorithms along with illustrative algorithms. Proofs of correctness of algorithms are also included when it is appropriate to do so. Finally, I have tried to present all the material in the book with a suitable amount of mathematical rigor.