Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

An Extreme Example of Space Optimization

February 01, 2012

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, 2n— 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 2n 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 2n elements, which would take O(2n) 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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video