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.
 

Comments:

ubm_techweb_disqus_sso_-a85191d836c18abc4f93f8a71a73477b
2012-02-08T20:14:37

I suppose if we have the answer, we shouldn't post it?


Permalink
ubm_techweb_disqus_sso_-db1d7e7bfe35be7f0dbe40455322b280
2012-02-03T22:36:44

Isn't directed graph connectivity NL-complete (so you need O(n^2) space to calculate it)?


Permalink
Zenju
2012-02-03T12:03:48

> 2n elements, which would take O(2^n) space to store.
I think this should be O(2^n * n).

> solve this problem
The O(n) really is a hard constraint as it rules out recursion, due to stack space limitations.
I think there is one interesting "solution" which respects O(n) memory, but has possibly the worst run-time:

Start with p and test whether a connection exists to a randomly chosen point. If "yes", take this point as new reference and iterate. If we happen to meet "q" by the way we're done.
If "no", restart from the very beginning.

Depending on "how reliable" our answer shall be, we can throw in sufficient amount of time. In other words, if we allow an infinite amount of time, we'll get the 100% reliable answer whether a path exists.
Therefore runtime will be O(inf) in worst case.


Permalink
ubm_techweb_disqus_sso_-045cc041748369091305089a426d1b37
2012-02-02T18:24:25

Of course the first thought is to start at the end ("q") and work your way back to "p", but I suppose that is why you mentioned the whole "p may be connected to q, but q is not necessarily also connected to p".


Permalink
ubm_techweb_disqus_sso_-d1857827c4489c42613ad58d5c7f89ef
2012-02-02T15:36:51

I assume that we can't use recursion either, as that is just another way to consume memory; so its down to iteration?


Permalink
ubm_techweb_disqus_sso_-d53a7b6c2d79c7a5d7104db7b43e0e02
2012-02-02T02:20:42

Anything to do with digraphs O(n^2)?


Permalink


Video