Not understanding some basic rules of mathematics or logic can be a problem if you are a computer programmer. It can stand in the way of a good solution to a problem, or worse yet, can cause you to spend a lot of time working on a dead end. In the case of New Zealand [...]

read more from this topic.....

You may have never heard of Vinay Deolalikar, but there is a chance that he may become next year’s Turing Award winner, not to mention an overnight millionaire. It seems that Vinay dropped the news at the start of this week that he had proven that P does not equal NP. In short, this proof [...]

read more from this topic.....

Back in 1981, fresh out of school, I was awestruck by Steve Wozniak’s program that calculated over 100,000 digits of e on an Apple II. (Anyone who has a scan of his article in the June 1981 issue of Byte, please email me a copy!) Shortly after reading the article, I ported his program to [...]

read more from this topic.....

The Pigeonhole Principle, also referred to as the Counting Theorem, is a handy tool for mathematicians, and naturally, computer programmers. The loose version of this principle says “After placing n pigeons into m compartments, if n is greater than m, you will find that some compartment must contain more than one pigeon.” Seems obvious, and [...]

read more from this topic.....

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 of Watch me solve it better, faster, and with [...]

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 a useful replacement for bounding boxes. Visual pattern [...]

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.....