Algorithm Design Manual

On the forty-second page of “Algorithm Design Manual” author Steve S. Skiena wrote (emphasis added):

with the priority queue, we built a data structure capable of a wider range of operations.

Although there were various other complications, such as quickly recalculating the length of the strips affected by the peeling, the key idea needed to obtain better performance was to use the priority queue. Run time improved by several orders of magnitude after employing these data structures.

How much better did the greedy heuristic do than the naive herustic? Consider the table in Figure 2-8. In all cases, the greedy heuristic led to a set of strips that cost less, as measured by the total size of the strips. The savings ranged from about 10% to 50%, quite remarkable, since the greatest possible improvement (going from three vertices per triangle down to one) could yield a savings of only 66.6%.

After implementing the greedy heuristic with our priority queue data structure, our complete algorithm ran in O(n - k) time, where n is the number of triangles, and k is the length of the average strip. Thus the torus, which consisted of a small number of very long strips, took longer than the jaw, even though the latter contained over three times as many triangles.

There are several lessons to be gleaned from this story. First, whenever we are working with a large enough data set, only linear or close to linear algorithms (say O(n lg n)) are likely to be fast enough. Second, choosing the right data structure is often the key to getting the time complexiy down to this point. Finally,

More information about “Algorithm Design Manual” (and the book itself) is available from:

• Barnes & Noble
• Amazon.com
• Powell's Books

(Springer, July 1998. Hardcover, 486 pages. ISBN: 0387948600; EAN: 9780387948607.)