Software development, .Net, SQL Server, TDD, Agile, Community and other Odds and Sods
Mitch Wheat has been working as a professional programmer since 1984, graduating with a honours degree in Mathematics from Warwick University, UK in 1986. He moved to Perth in 1995, having worked in software houses in London and Rotterdam. He has worked in the areas of mining, electronics, research, defence, financial, GIS, telecommunications, engineering, and information management. Mitch has worked mainly with Microsoft technologies (since Windows version 3.0) but has also used UNIX. He holds the following Microsoft certifications: MCPD (Web and Windows) using C# and SQL Server MCITP (Admin and Developer). His preferred development environment is C#, .Net Framework and SQL Server. Mitch has worked as an independent consultant for the last 10 years, and is currently involved with helping teams improve their Software Development Life Cycle. His areas of special interest lie in performance tuning
Thursday, August 27, 2009
A programmer’s knowledge of algorithms can be (very) roughly divided into 3 categories:
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.
MSN, Email: mitch døt wheat at gmail.com