You are here

Practical Analysis of Algorithms

Dana Vrajitoru and William Knight
Publication Date: 
Number of Pages: 
Undergraduate Topics in Computer Science
[Reviewed by
Dale Skrien
, on

Practical Analysis of Algorithms is a textbook for an advanced undergraduate course. It differs from many other analysis of algorithms texts in that it is mathematically rigorous. That is, it precisely defines all terms and proves almost all of the theorems that it uses. In particular, chapters 1–4 (167 of the book’s 452 pages of text) concern discrete mathematics with scant computer science motivation, and the remaining chapters 5–7, which are devoted to specific algorithms, have a significant number of proofs in them. In the preface, the authors state, “This textbook addresses the needs of collegiate computing programs without assuming a strong mathematical background.” However, students will need to have enough mathematical background to be able to understand the proofs, many of which are non-trivial. Also, many of the exercises ask the students to prove statements, and so a prior course in mathematical proof techniques is essential in my view.

Although the book is about algorithms, it does not cover some topics that are typically included in an analysis of algorithms course. For example, it does not discuss dynamic programming algorithms. Also, it only mentions greedy algorithms in the last two pages of the last chapter. Moreover, it does not mention the complexity classes of P and NP and their impact on finding optimal algorithms for problems.

In some ways, the book is more of an advanced data structures book than an analysis of algorithms book. Most of chapter 5 is devoted to covering basic data structures and chapter 7 covers basic graph algorithms, many of which are typically covered in a data structures course. The main difference between the material covered in those chapters and the material covered in a typical American data structures course is the textbook rigorously proves the properties of these data structures.

Other notes of interest:

  • Every section has lots of examples and lots of good exercises.
  • Given the thoroughness with which the authors prove the mathematical results that they later use, I think the book would make an excellent reference book for a library.
  • The index is very inadequate. It is only 2 pages long and so misses many terms defined in the book. For example, Section 5.6 is about priority queues and binary heaps, but the terms “binary heap”, “min heap”, and “max heap”, all of which are defined in that section, are not mentioned in the index.
  • All the sample code is in C++.
  • The only supplementary materials that are available on the publisher’s web site are slides and a solutions manual.

In summary, the book straddles the line between a rigorous discrete mathematics textbook, an advanced data structures textbook, and an analysis of algorithms textbook. The risk of such an approach is that computer scientists may not be interested in it because so much of the book is devoted to proofs and mathematicians may not be interested in it because, although it covers a lot of the basics of discrete math, most of the book is about algorithms.

Dale Skrien is a computer scientist and was formerly a mathematician. He currently teaches at Colby College.