CLRS Algorithms book review and implementations
📅June 06, 2020 | ☕️5 minutes read
This post is devoted to the CLRS book and the implementation of algorithms discussed in the main body text.
A short book review
It is hard to express how much I can recommend this book. My first contact with this masterpiece was in the high school, while I was trying to study algorithms for competitive programming. I could obtain some knowledge, but I was not ‘mathematically literate’ to appreciate the rigour and algorithm analysis discussions. Couple of years later, it was the university algorithms course textbook, and I could truly understand the material explained here. After the University reading experience, I have decided to (re)visit the most important topics. For me, this is possibly the ‘the best’ of algorithms and data structures resources available. I think the best part is algorithm analysis, not the actual pseudocode which is sometimes hard to read. Analysis is usually very formal and many proofs regarding the complexity and correctness are extremely clear and usually very rigorous. I consider the pseudocode the only drawback and the fact the book uses 1-based array indexing (CLRS, why this?).
The authors clearly explain the need for certain algorithms and data-structures and discuss both theoretical and practical aspects.
Almost all sections have the accompanying exercises, thoroughly testing understanding. Some of them can be very interesting, usually end of chapter problems are hard. For example, after Red Black Trees chapter, AVL trees appear as an exercise to the reader {‘<3’}.
My favourite parts are Heaps, Hash-Tables, the whole Graph Algorithms section and Dynamic Programming section. Personally, I found it very difficult to grasp dynamic programming concepts, but this textbook really explains it properly. There are plenty of worked-out examples, each thoroughly discussed with proofs regarding correctness, running time and even the practical implementation advice.
To sum up, there is also the accompanying online course taught at MIT. Learn more here.
Although it is not an easy read, I think it is one of ‘must reads’.
CLRS Implementations Project
In this project, I have decided to focus only on the main text pseudocode and more interesing exercises. All implementations are written in C and should be cross-platform. Here is a link to the project github repository.
The folder structure of the project was made to resemble the book structure. Usually, implementations come with small auxiliary programs and simple test inputs.
For example, along with an implementation of Huffman coding algorihm there is a small program to print the generated prefix code.
Also, although the pseudocode in the book may not have the best variable naming, I have decided to respect it for the sake of consistency. However, I did not respect pseudocode conventions when it comes to implementations of algorithms presented as exercise problems or as end of chapter problems.
I have covered the following chapters:
My Favorite Algorithms
Here, I will list a few of the most interesting algorithms I encountered in the textbook.
Huffman codes 🔗 - a beautiful greedy ‘construction’ algorithm
printing neatly 🔗 - a neat, non obvious application of dynamic programming
constructing an optimal binary search tree 🔗- a nice application of DP on trees
constructing an Euler tour with Hierholzer’s algorithm
🔗 - a nice ‘construction’ graph algorithm, challenging to implement in C. Presented as one of end of chapter problems.
scheduling lectures with interval graph coloring 🔗 - a nice, real world application of greedy activity scheduling. Presented as one of exercises.
topological sorting of a ‘clothing’ graph 🔗 - a nice ‘real-world’ example of topological sorting graph algorithm