Algorithms

December 18, 2008 - zenoconsultingzenoconsulting


Algorithms are one of the core tenets of computer science. A lot of people write software. Some are really good at it. Some are really bad at it. I think that having a good grasp of algorithms will definitely help one fall into the former category.

I find that mastering anything takes a lot of practice, and a lot of good references to draw from. Sure, I had an algorithm analysis class at University, but I don't think any one course can get you there. It is more like a launch-pad to get you to invest more in yourself.

There is no shortage of texts on algorithms, but I find they vary wildly in their practicality. The Knuth tomes are probably the most famous, and also the most terse reading you'll likely encounter. Not to take anything away from Knuth, because he is undoubtedly a brilliant man who has contributed a great deal to computer science, but I just don't dust the cover from his books that much.


21zywE7G5cL._SL160_PIsitb-sticker-arrow-dp,TopRight,12,-18_SH30_OU01_AA115_.jpg
A more practical book I do like to read often is The Algorithm Design Manual by Steven Skiena. Consider this book like the GoF design patterns edition for algorithms. The first half of the book describes data structures and algorithms, and the second half provides a library of algorithm problem-spaces and proposed algorithmic solutions and trade-offs. In that sense, it is fantastically useful. Skiena also has several "War Stories" where he reiterates real problems for clients, and how he went about solving the problem by applying a particular algorithm. It avoids the terse math, and makes for great bedside reading. The book does not go into code or implementations — so depending on your language of choice, you'll want to complement it with something else.
51HG4K50R1L._SL160_AA115_.jpg
If you are looking for implementation in C, my favorite books are Algorithms in C Pts. 1-5 by Robert Sedgewick. Sedgewick was a student of Knuth. This series is pretty exhaustive in its treatment of both theory and implementation. He implements each of the various data structures using ADT (abstract data types), and goes in depth on how they can be applied to solve various problems. If C isn't your bag, he has essentially morphed only the implementation (with the core text being the same) for both Java and C++. I don't have the C++ edition, so I can't comment on that, but the Java version — while still really interesting, implements the code in a strictly procedural way. It seems as if someone with a strong C background and a limited Java background was asked to port the code over. This is fine, as it is still very readable, and understandable.
51TSHtxrQZL._SL160_AA115_.jpg
A very nice, short, concise primer on algorithms is the aptly titled Algorithms by Sanjoy Dasgupta, et al. The text is a mere ~300 pages, but it is packed full of content. The book is pure theory — no implementation at all.
615MSAW2RXL._SL160_AA115_.jpg
A more complete treatment can be found in Introduction to The Design & Analysis of Algorithms 2nd Ed. by Anany Levitin. This is surely a college course text. It does a great job at covering all the relevant algorithmic topics in an unpretentious, readable manner. I like to take the shorter, lighter Algorithms book with me on plane trips purely for logistical reasons, but when I want more depth on a topic, I pick this book up.

Those are my favorite books on the topic. The only other thing I wanted to mention is a technique I use for learning that I've found works very well. Algorithms can be a somewhat difficult topic for many people. When I learn, I find the most effective way is to read the same topic from several different books. I don't read text books cover-to-cover. I'll pick a topic (e.g. graphs), and I'll read a chapter on graphs from one book. The next night, I'll read the same topic from a different book, etc. Each time you read it, it reinforces what you already read the night before so the reading gets easier. Also, you get to hear treatment of the same topic from a different author's perspective — which often opens up new understanding. Finally, after I've read several different versions of the same topic, I'll sit down and bang out some code. For example, I'll build up the Graph ADT that Sedgewick lists in his book, and then I'll extend it, or take a stab at solving some of the sample problems from any of the books.

One of the reasons I'm on an algorithm kick lately is…well a) it is fun because I am a computer science dork and b) I am thinking ways to help me learn functional programming in Haskell and/or Erlang. I've been reading these two books lately:

41rwtENNgBL._SL160_PIsitb-sticker-arrow-dp,TopRight,12,-18_SH30_OU01_AA115_.jpg
41XOOpdBzKL._SL160_AA115_.jpg

…and one way I thought it might be fun to challenge myself is to try to do something like build a graph library in one of these languages.


Backlinks


Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License