For the last few months I’ve been up to my eyeballs in algorithms - school, work, writing, you name it.
In honor of the often puzzling topics I’ve been working on, here’s a little crossword with an algorithms theme.
The java applet that lets you solve online has a bit of lameness, but it’s not […]

read more from this topic.....

Dr. Dobb’s PortalNovember, 2007
Article on DDJ site

As I’ve confessed in the past, I’m a sucker for word puzzles. My recent post on a Will Shortz puzzle from NPR Morning Edition ended up provoking a surprising amount of comment, much of it in the vein […]

read more from this topic.....

Dr. Dobb’s PortalSeptember, 2007
Article on DDJ site

Finding the Convex Hull of a set of points is an interesting problem in computational geometry. It is useful as a building block for a diverse set of applications, including thing such as:

Collision detection in video games, providing […]

read more from this topic.....

This article discusses the use of C++ hash containers to improve storage of subproblem results when using dynamic programming (DP.) Memoization is a key part of dynamic programming, which is conventionally done by storing subproblem results in simple tables or lists. Using hash tables instead of these simpler structures will allow you to use dynamic programming while retaining your algorithm’s natural recursive structure, simplifying design and making your code easier to follow. I’ll provide a fully-developed example of an algorithm, and show how it can be adapted to use hash table memoization.

read more from this topic.....

It seems like this is the summer of multicore panic. I can’t open a technical magazine without some pundit declaring that our current programming paradigms are useless when running on new multicore CPU architectures. Venerable analyst John Dvorak, who generally actually understands what he is writing about, coughed up this mess (with minor excisions for […]

read more from this topic.....

This article presents the algorithm that solves the Byzantine General’s Problem, as first described by Lamport, Pease, and Shostak in 1982 [1]. While Lamport’s algorithm is not particularly complex, programmers who aren’t used to working on distributed computation might find it difficult to implement. To accompany the explanation of the algorithm, I have included a C++ program designed for experimentation with the solution.

read more from this topic.....

Dr. Dobb's PortalApril, 2007
Article on DDJ site

I'm an inveterate fan of wordplay of all sorts - puzzles, anagrams, crosswords. I've been known online by my anagrammatic name, SnorkelMan, all the way back to the ancient days of the text mode BBS. My continual hectoring [...]

read more from this topic.....

There are a lot of classic papers in Computer Science, Information Theory, and so on that aren't commonly availably outside of university libraries. That is, unless you happen to visit Babar K. Zafar's web site.

read more from this topic.....

Suffix trees provide the extraordinary ability to search through an unlimited amount of text for a given string of length N in O(N) time. This article describes the structure of a suffix tree and provides C++ source for a simple suffix tree generation algorithm.

read more from this topic.....

An example of how to use STL priority queues, with an implementation of Huffman coding as an example.

read more from this topic.....