Wednesday, July 2, 2008

Algorithms: Design Techniques and Analysis (Lecture Notes Series on Computing, Vol 7)

Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
The book represents a well written, consistent and easy to follow view on the area of algorithm analysis. It gives an excellent overview of various mathematical and computer science areas, including but not limited to combinatorial geometry, NP-problems, complexity theory, graph theory, algorithm analysis, dynamic programming and even computational geometry.

Most of the chapters are intended for a senior level undergraduate and graduate student, but some (such as part 4 devoted to complexity problems) are more suitable for "mature" audience and require some preliminary knowledge in the area.

I found chapters on sorting, data structures, recursion and functional programming well written and structured, and examples to be practical as well as informative.

Sections on amortized analysis, randomized algorithms, approximation algorithms and iteration improvement deal with current directions in the algorithmic research and provide an excellent overview of the "state-of-the-art" in these areas. I also enjoyed reading through the section on greedy algorithms (shortest path and minimum spanning tree problems).

Section on computational complexity and analysis of the relationship between complexity classes seems to be a bit complicated, those who are interested in this area should probably do some preliminary reading.

The last section on computational geometry (my area of expertise) and applications of Voronoi diagrams could be extended, but even in the current state it givs a pretty good idea of what computational geometry is all about.

Overall, I give to this book a "5 star" review and recommend it for anyone who is seriously interested in learning exactly how algorithm design and analysis work. I thoroughly enjoyed reading this book and can only wish that author would write more books like that in the future!