[2009-03-15] “Data Structures And Algorithms”

“Data Structures and Algorithms” by Alfred Aho, Jeffrey Ullman and John Hopcroft is a relatively-short introductory text for data structures and algorithms useful for computer programming. It covers a surprisingly-broad set of topics considering its size. It is fairly dated now but it still has all the essential data structures, algorithms and algorithm analysis techniques.

Early on in the book the authors describe algorithm analysis techniques and the effect of badly-designed algorithms on performance as the size of the input data increases. They also introduce the concept of an Abstract Data Type (ADT) and use it to describe various data structures. The algorithms are described using a pseudo-language that is a bit too similar to Pascal - programmers these days will find it a bit weird and distracting, though it is still close enough to the currently popular programming languages like Java or C++ for easy translation.

If you are an absolute novice, this might not be a good book with which to start the study of data structures and algorithms. It does not clearly explain why you need to study so many data structures and under which constraints you would prefer one over the other. It also leaves many of the details of the algorithms to be worked out by the reader. There are no solutions provided for the exercises given in the book. Many a time the book uses unnecessarily formal descriptions when a much simpler language would have sufficed.

Some of the “advanced” data structures like red-black trees, AVL trees, splay trees, etc. are either not described here or are just alluded to without any details. An important and basic algorithm like binary search through sorted data is only mentioned in passing. There is not much information on either parallel or cache-friendly algorithms, both of which are important on modern systems.

If you are already familiar with the basic data structures and algorithms and do not want to carry around some of the other unwieldy tomes on this subject, this is a good book to have around as a refresher. If you need a comprehensive up-to-date treatise on the subject, this is not quite the book.

Other Posts from 2009