[2010-03-22] “Introduction To Algorithms”

I put off reading Introduction to Algorithms by Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein (popularly known as “CLRS”) for quite some time because I was somewhat intimidated by its bulk. The recent release of the third edition of this tome finally made me get a copy and give it a dekko. This compendium of a number of algorithms and data structures for computer programming is bulkier than its predecessors, but it does not disappoint. It should serve as a good reference for this field, though not quite as an introductory text for beginners. A serious professional will have a copy handy at all times. Somewhat surprisingly, it does manage to leave out some commonly-encountered data structures and algorithms, so it is not as comprehensive and up-to-date as I would have liked.

With 35 chapters and four appendices, this book packs in a lot of material. The main content is divided into eight parts, beginning with the foundations of algorithm design and analysis and ending with a set of special topics. Many of the algorithms are presented in pseudo-code that can readily be translated into an imperative language of your choice. Most such algorithms are also analysed for running costs, usually by solving the appropriate recurrence relations. The mathematics used in the analysis is not that complicated and the appendices refresh your memory in case you have forgotten it since high-school or college. The notation used throughout the book is thankfully one that is now widely used.

Despite its name and the claims of the authors in the preface, this book is not suitable for absolute beginners to the subject. In most places it just assumes that you know the basic concepts and proceeds to expand on them. It does not clearly explain to the beginner why they need to study so many data structures and algorithms and how to choose an appropriate data structure or algorithm. Somewhat surprisingly for a book on the subject, it does not tell you what is an Abstract Data Type (ADT). The authors use the term “dynamic set” instead of the more common “collection” and this might unnecessarily confuse some people.

I was surprised to find many a commonly-encountered data structure or algorithm missing from this modern tome. For example, trie, skip list, splay tree, dancing links, A*, Judy array, etc. are either not mentioned at all or are referred to merely in passing. Looking at the current trends in computer architecture, it is high time such books explain some cache-oblivious algorithms that can run efficiently on modern CPUs. The chapter on multi-threaded algorithms also seems to have been added as an afterthought. For example, it does not talk about super-linear speed-ups that are possible with concurrent algorithms. Finally, we have to increasingly deal with huge data-sets that do not fit into a single computer's RAM or even hard-discs - learning to efficiently store and process such data is important in modern computing (just as it was in the old days) and a book like this cannot afford to leave it out.

Unlike many other text-books, the problems in the exercises further explore the topics introduced in the associated section instead of merely testing the reader's comprehension, some times providing more details or introducing a variant. Some of the problems use mostly-funny names for professors - the authors provide explanations for these names in case you don't “get it”. The bibliography is quite extensive and useful when you want to find more information about a given topic.

Other Posts from 2010