Thursday, August 27, 2009

 

Algorithms

A programmer’s knowledge of algorithms can be (very) roughly divided into 3 categories:

  1. Essential: Basic knowledge of the algorithms you use in your day-to-day work (hopefully, along with their ‘Big Oh’ Complexity, although it is surprising how often this is lacking…)
  2. Desirable: Knowledge of a wide range of algorithms, including sorting, searching, graph algorithms etc.
  3. Rarely Required in a Business Setting: Ability to Analyse an Algorithm’s Complexity

Now, I’m obviously not advocating that all programmers should be algorithm guru’s, but if you want to broaden your knowledge, here are a few places to start:

One of the classic Introduction to Algorithms books is Sedgewick’s Algorithms This used to be a single book (the format I read it in), but is now split into two volumes. It comes in various (computer) language versions, including C++: Fundamentals (parts 1-4) and Graphs (part 5). It is accessible, and covers most of the common algorithms you are likely to encounter (or need).

Another classic introductory book on the subject is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein (sometimes referred to as CLRS).

For an excellent free resource, check out the Introduction to Algorithms course on MIT OpenCourseWare (which uses CLRS as the course text; one of the authors, Prof. Leiserson, taught the course at MIT): MIT 6.046J / 18.410J Introduction to Algorithms

The course materials also contain video lectures. Here’s an example of why having at least some broader knowledge of algorithms and their application is useful: The skip list is a little known data structure (possibly because it is a relatively recent invention), and yet it is extremely useful and much easier to implement from scratch than many of the other balanced data structures: This is described in lecture 12.

Two books that are lighter and less formal are Algorithms in a Nutshell and the Algorithm Design Manual (Second Edition). Instead of formal mathematical proofs these books take a more practical approach, with real world problems and their solutions. They also show you how to estimate and measure the complexity of a solution. Both books are good, practical reference guides for programmers (I’m just about to add the Algorithm Design Manual to the Perth .NET User Group library…). Highly Recommended.

If you want something more advanced, then try these MIT OCW courses: 6.854J / 18.415J Advanced Algorithms, and the more mathematically advanced: 18.409 Topics in Theoretical Computer Science: An Algorithmist's Toolkit.

For learning how to analyse algorithms (and let’s be honest, it will be a rare event that you actually have to!), another of Sedgewick’s books, An Introduction to the Analysis of Algorithms, is a good place to start. A more advanced text is Concrete Mathematics: A Foundation for Computer Science and of course Knuth Volumes 1 - 3 (and the remaining volumes, which Knuth is releasing as ‘fascicles’…) which are not for the faint hearted and require considerable mathematical knowledge as a pre-requisite.



    

Powered by Blogger