REVIEW - Data Structures and Algorithm Analysis in C++


Data Structures and Algorithm Analysis in C++


Mark Allen Weiss



Addison-Wesley (2006)




Frances Buontempo


November 2008




This book provides a thorough introduction and in depth look at how to define the complexity of an algorithm and then goes on to look a various structures including lists, stacks, queues and trees. The algorithms encompass sorting, disjoint set classes (i.e. equivalence relations) and graphs. Various techniques such as greedy versus divide and conquer, randomised and backtracking algorithms plus dynamic programming are detailed. A clear, in depth explanation of amortized analysis is presented and finally other specialised data structures such as splay trees, red-black trees, skip lists, other trees, traps, and pairing heaps are covered.

Prior to this, the book starts with a hit and run overview of C++ (including classes, std::vector and std::string, pointers, parameter passing, templates and functors) and mathematics (exponents, logarithms, series, modular arithmetic and proofs). Prior to starting a computer science course, a friend with advanced-level school mathematics background worked through the revision mathematics session with me. Suffice to say it served as a good basis of things to learn but was too sparse and terse to be of any use other than as a pointer to which topics to pursue in another book. The same is true of the C++ introduction, though the author lists all the right books for a C++ rookie to buy and read.

Introductory chapter aside, this book is very well written, and given the in-depth technical content, a pleasure to read. The algorithmic analysis gives detailed mathematical proofs, for example of the complexity of operations on a variety of data structures. Without a strong mathematical background or some determination, this could prove heavy going but worth it. The illustrations frequently manage to convey some complicated ideas with clarity. There is enough sample code to build examples to pursue the ideas further, but this does not distract from the main narrative as can happen with some books.

The majority of the material covered in this book is probably amply covered elsewhere (Knuth springs to mind). Nonetheless it pulls together a neat selection of ideas and presents them in a format that can be read in a few (determined) sittings. The introductory chapter will be little use to beginners and of limited value for those in the know, but apart from that this is a good book.

Recommended with the reservation: buy if you can afford it and don't already have Knuth or similar, or have Knuth and can't manage to read it from cover to cover but wanted to.

Book cover image courtesy of Open Library.

Your Privacy

By clicking "Accept Non-Essential Cookies" you agree ACCU can store non-essential cookies on your device and disclose information in accordance with our Privacy Policy and Cookie Policy.

Current Setting: Non-Essential Cookies REJECTED

By clicking "Include Third Party Content" you agree ACCU can forward your IP address to third-party sites (such as YouTube) to enhance the information presented on this site, and that third-party sites may store cookies on your device.

Current Setting: Third Party Content EXCLUDED

Settings can be changed at any time from the Cookie Policy page.