CS3343/3341, Bolts and Nuts

CS 3343/3341
Analysis of Algorithms
Spring 2012
Weird Topic

Bolts and Nuts

Quotation: The first nuts and bolts appeared in the middle 1400s. The bolts were just screws with straight sides and a blunt end. The nuts were hand-made, and very crude. When a match was found between a nut and a bolt, they were kept together until they were finally assembled. In the Industrial Revolution, it soon became obvious that threaded fasteners made it easier to assemble products, and they also meant more reliable products. But the next big step came in 1801, with Eli Whitney, the inventor of the cotton gin. The lathe had been recently improved. Batches of bolts could now be cut on different lathes, and they would all fit the same nut. Whitney set up a demonstration for President Adams, and Vice-President Jefferson. He had piles of musket parts on a table. There were 10 similar parts in each pile. He went from pile to pile, picking up a part at random. Using these completely random parts, he quickly put together a working musket. -- Karl S. Kruszelnicki (`Dr. Karl'), Karl Trek, December 1997

Quotation: The first nuts and bolts appeared in the middle 1400s. The bolts were just screws with straight sides and a blunt end. The nuts were hand-made, and very crude. When a match was found between a nut and a bolt, they were kept together until they were finally assembled. In the Industrial Revolution, it soon became obvious that threaded fasteners made it easier to assemble products, and they also meant more reliable products. But the next big step came in 1801, with Eli Whitney, the inventor of the cotton gin. The lathe had been recently improved. Batches of bolts could now be cut on different lathes, and they would all fit the same nut. Whitney set up a demonstration for President Adams, and Vice-President Jefferson. He had piles of musket parts on a table. There were 10 similar parts in each pile. He went from pile to pile, picking up a part at random. Using these completely random parts, he quickly put together a working musket. -- Karl S. Kruszelnicki (`Dr. Karl'), Karl Trek, December 1997

The Puzzle:

A disorganized carpenter has a mixed pile of bolts and nuts and would like to find the corresponding pairs of bolts and nuts. Each nut matches exactly one bolt (and vice versa). By trying to match a bolt and a nut the carpenter can see which one is bigger, but she cannot compare two bolts or two nuts directly. Can you help the carpenter match the nuts and bolts quickly?

First Answer:

Suppose there are n nuts and n bolts. We can take the first nut and go through the bolts looking for a fit. In the worst case we try n - 1. (If the first n - 1 bolts don't fit, we know without trying that the last one will fit.) Now we go to the next nut and fit it to a bolt in n - 1 tries. So in the worst case this requires

(n-1) + (n-2) + ... + 3 + 2 + 1 = (n-1)(n-2)/2

This method is a Θ(n²) algorithm.

A Better Answer:

Pick a random bolt, compare it to all the nuts, find its matching nut and compare it to all the bolts, thus splitting the problem into two problems, one consisting of the nuts and bolts smaller than the matched pair and one consisting of the larger ones. Repeating in this manner yields an algorithm whose expected running time can be analyzed by imitating the known analysis for Quicksort. This is like your text's Randomized Quicksort algorithm, where the pivot is chosen at random. It's expected running time is Θ(n log(n)), while it's worst-case running time is still Θ(n²).

[Wording taken from this source.]

Revision date: 2012-01-06. (Please use ISO 8601, the International Standard Date and Time Notation.)