When people talk about optimization, they usually mean making programs run faster. Many ways of doing so, such as caching and precomputing results that will be used more than once, gain time at the expense of extra memory. Today I want to talk about an example that goes in the opposite direction: sacrificing time to gain space.

The example comes from an exam in an algorithms course many years ago. Suppose you have a very large number — say, 2ⁿ— of points. Each of those points may or may not be connected to any of the other points. You can determine whether point p is connected to point q by calling a function path(p, q), which will return true or false. If p is connected to q, that says nothing about whether q is connected to p. It might be connected, or it might not. Because there are 2ⁿ points, we will assume that all integers are n bits long and unsigned, so that any integer can store the number of any point, but no more than that.

The problem is to write a program that takes two points p and q, and determines whether there is a path between them — that is, whether there is a sequence of one or more points in which p is the first point, q is the last point, and each point except the last is connected to its successor.

In principle, this problem is not difficult. For example, we can create an array with one element for each point. That element will eventually tell us how many steps it takes to reach the corresponding point from p, or will 0 if we have not yet found a path from p to that point.

We start by finding all the points to which p is connected directly and giving those points the number 1. Then we look at the direct connections from each of those points, giving those points the number 2 unless they are already numbered 1; and so on. Eventually, we will get to a state in which either we have given a number to q, in which case we have found a path; or we go through all of the points without changing anything, in which case no path exists.

The exam question had a sadistic extra wrinkle that ruled out this kind of straightforward solution: The program was not allowed to use more than O(n) space, measured in (n-bit) integers. In other words, the students were not even allowed to use enough memory to store the entire contents of a single path — because a path might have as many as 2ⁿ elements, which would take O(2ⁿ) space to store.

Can you figure out how to solve this problem? If you can, how fast (and by fast, I really mean slowly — at least in this case) does it run? I'll reveal the answers next week.