A while ago I wrote about the playground ritual of choosing teams for a ball game. The simplest algorithm has two captains, A and B, who take turns choosing players until everyone is assigned to one team or the other. Call this the ABAB algorithm. Donald B. Aulenbach suggested a very easy modification that produces more closely matched teams. Aulenbach’s proposal is the ABBA algorithm, where A gets the first pick in the first round but B goes first in the second round, and they continue alternating in successive rounds. (Another way of describing the same process is that A begins with a single turn and thereafter both captains take two turns in a row.)

For a quantitative model of this process, let’s suppose each player’s ability is represented by an integer chosen uniformly at random from the interval 1 through m. We’ll let the total number of players, n, always be even, so that the two teams will be of the same size. After we have divvied up all the players, we sum the strengths of the two teams and calculate the discrepancy—the absolute value of the difference. Stephan Mertens of the the Otto von Guericke Universität in Magdeburg (who put me onto this problem in the first place) has shown that the expected discrepancy for the ABAB algorithm is m/2 × (n–1)/n; thus as n becomes large the discrepancy approaches m/2.

What about the ABBA algorithm? Here are some numerical results:

                         discrepancy

  n        m       ABAB     ABBA     exact

  4        4        1.4      0.7       0.7
  6        8        3.4      1.4       0.9
  8       16        7.0      2.3       1.2
 10       32       14.7      4.2       1.7
 12       64       29.2      7.2       2.3
 14      128       59.5     13.7       3.6
 16      256      122.4     23.9       5.7
 18      512      244.6     47.6       8.4
 20     1024      490.6     90.6      14.2
 22     2048      970.4    168.9
 24     4096     1944.9    315.7
 26     8192     3972.5    621.5
 28    16384     7907.9   1177.9
 30    32768    15892.6   2291.4
 32    65536    31877.2   4520.0

For each line of this table I ran the ABAB and ABBA algorithms on 1,000 randomly generated sets of numbers with the indicated values of n and m, then averaged the results. Up to n=20 I also found the optimum partitioning of each set, by a brute-force enumeration. The values of m are chosen so that log₂m = n/2. Most sets with these values of m and n have many perfect partitions, with discrepancy zero—but of course neither the ABAB nor the ABBA algorithm is guaranteed to find these ideal solutions.

Here are the same data in graphic form:

Clearly, ABBA is superior to ABAB, just as one might expect.

Questions:

1. What is the expected discrepancy of the ABBA algorithm, as a function of n and m?
2. Is ABBA the optimal algorithm of its type? Of course it is not the best of all algorithms; brute-force enumeration is better, at the cost of exponential computing time. There are also superior heuristics, but they cannot be implemented with a fixed sequence of choices, determined in advance. ABBA is a “blind” algorithm: It applies the same sequence of operations to all sets of data. Is there any other blind algorithm that outperforms it?
3. The uniform random distribution of abilities is probably not very realistic; a normal distribution would be more plausible. Would this make any difference in the performance of the algorithms?
4. Surely someone has worked on this problem before?

Going back to my own childhood, I don’t think the kids in my neighborhood ever discovered the ABBA algorithm. We did recognize the inherent advantage of choosing first, and we compensated by adopting a separate ritual to decide who got the first pick. In baseball, this involved a hand-over-hand struggle for a grip on the bat. Sometimes I think the preliminaries were more fun than the game.

The March-April issue of American Scientist is now available on the Web; paper copies should be on their way soon. My column is about hump yards and turnouts and wyes—in other words, about algorithms for railroad workers. “Computing with locomotives and box cars takes a one-track mind.” There’s a small puzzle near the end of the column. You’re welcome to post comments, complaints and solutions here.

In the new issue I also recommend a “Macroscope” article on Avogadro’s number by Ronald M. Fox and Theodore P. Hill of Georgia Tech. For those who have forgotten their chemistry, Avogadro’s number is the number of molecules in a mole of a substance (an amount in grams numerically equal to the molecular weight). Specifically, N_A is defined as the number of carbon atoms in 12 grams of carbon-12, and its value is roughly 6.02 × 10²³. Fox and Hill suggest turning the definition upside-down: Instead of trying to count the atoms in a gram, define the gram as a certain number of atoms. They have a specific number to recommend: 602,214,141,070,409,084,099,072. I invite you to deduce what’s so special about this particular number and why they favor it over other candidates in the same range.

There was a line at the Post Office window, so I went to the self-service counter, plopped my letter on the scale, and found that it weighed a whisker under two ounces. I bought stamps from the machine and stuck on a 39-cent and a 24-cent. I was just about to drop the letter in the slot when a thought struck me. I went back to the scale. Sure enough: With the stamps affixed, I was over the two-ounce limit.

I’m not going to tell you what I did next—whether or not I put an extra stamp on the envelope. That’s between me and my postmaster, and until they repeal the Fifth Amendment I have nothing more to say about it. But I will concede that my conscience may have been troubling me, because last night I dreamed of postal reform.

In my dream, the nation finally scraps the whole bizarre congeries of ad hoc step functions that currently define U.S. postage rates. Postage becomes a continuous function of a letter’s weight. (The current rate structure for domestic first-class mail appears to be a feeble attempt to approximate a simple linear function: P = 24W + 15, with the weight W in ounces and the postage P in cents.)

In the new regime we also dispense with the baffling collection of arbitrary stamp denominations. (Currently on sale at shop.usps.com: 1, 2, 3, 4, 5, 10, 23, 24, 37, 39, 48, 60, 63, 70, 75, 83, 84, 87, 100, 385, 405, 500, 1440. (It’s not in the sequence server, and please don’t put it there.)) Sweeping away all this cruft, my dream Post Office sells postage in continuous strips and sheets with a defined value per unit area. You cut off a piece of the stuff—we can call it postage-tape, or maybe stampage—exactly as large as you need to pay the tariff on a letter of any given weight.

Better still, instead of measuring postage by the area of the stamp, we can measure it by the weight of the stampage stuff. The marvelous thing about this scheme is that the postage rate becomes a dimensionless quantity. Whether you express it in grams per gram or ounces per ounce, it comes out the same. The rate is a pure number. Let’s suppose it’s r = 1/10, just so we have something definite to talk about.

Now, when I take my letter to the Post Office, if it weighs, say, 50 grams, I know that I have to apply 5 grams of postage.

But wait. Now the letter-plus-stampage weighs 55 grams, and so the correct postage is 5.5 grams. When I add another half-gram of stamp stuff, the new weight is 55.5 grams, and the correct postage amount is 5.55 grams….

You may think that this endless series of adjustments to adjustments is a drawback of my new postal pricing model. Au contraire! It is the principal advantage. The benefits extend far beyond the Postal Service and promise to transform American life and culture, and especially education.

There is a scene that plays out every day in classrooms all across the country—or so I’m told. A high school kid, bored with a lesson on the summation of series, protests bitterly: “Why do I need to know this stuff? No way am I ever going to sum an infinite series in real life.” Now we have an answer for that young nihilist. Do you want to stand in the Post Office all day with cuticle scissors, cutting ever-smaller slivers of tape as you try to approximate the postage due on a letter? Or do you want to learn once and for all that

Here is America’s last best chance to be taken seriously as an educated and cultivated society. Nobody’s going to mess with a country where you need to know a little calculus just to mail a letter.

Addendum. Toward morning my dream took a darker turn. What if postal rates keep rising? Beyond, say, r = 1?

A new jeremiad foretelling the doom of computer science as an academic discipline has just been published by the British Computer Society. It’s by Neil McBride, principal lecturer in the School of Computing, De Montfort University, Leicester.

Some of what McBride says strikes me as breathtakingly wrong-headed:

Now vastly complex applications for businesses, for science and for leisure can be developed using sophisticated high-level tools and components. Virtual robots—Zooks—can be created by eight-year olds without needing programming, logic or discrete mathematics skills. Web designers build complex business sites, graphic designers build animations, accountants assemble business systems without needing to go object-oriented.

Computer science has lost its mystique. There is no longer a need for a vast army of computer scientists. The applications, games and databases that students once built laboriously in final year projects are bought at bookshops and newsagents.

If I understand this argument correctly, McBride is saying that computing (and in particular software development) has become so easy that there’s no longer a need for any sort of formal curriculum. Any eight-year-old can do it, or even an accountant. I wish I could believe that, but in fact I’d be inclined to argue in exactly the opposite direction: Computer science is in trouble not because all the big problems have been solved but because the problems are so hard that no one has a clue how to make any progress. In computing theory, the P = NP? question has been out there for almost 40 years, with no sign of resolution. In engineering, large software projects routinely run over budget and behind schedule. At a more personal level, maybe eight-year-olds in Leicester can conjure up virtual robots at will, but the rest of us struggle with computing environments that still seem overly complex, fragile, unreliable, inconsistent, and just plain buggy. I see no shortage of challenges for computer science.

Still, the underlying question is not to be shrugged off: Do computer science departments have a future in the university? Enrollments are down, and chairs are fretting about funding and the head count. Students, meanwhile, worry about finding a job. Those who began their education in the era of IPO frenzy have graduated into a more-somber world. (But James H. Morris and Peter Lee resist blaming it all on the boom-and-bust cycle in Silicon Valley; they point out that undergraduate enrollment peaked in 1987, and thus it was already falling long before the vulture capitalists began picking at the bones of dot-com failures.)

A few years ago, a committee formed by the National Academy of Sciencies and chaired by Mary Shaw of Carnegie Mellon University issued a spirited defense of computer science as a free-standing, independent area of research, distinct from mathematics, engineering and all other disciplines. More recently, Bernard Chazelle of Princeton University has been carrying on the campaign in a series of essays, editorials, and panel discussions. The following Q&A comes from a press release issued in advance of a panel discussion at the AAAS meeting last year:

Isn’t computer science really just a stepchild of mathematics?

As the recent breakthroughs on Fermat’s Last Theorem indicate, the field of mathematics has never been more fertile with new ideas. Mathematics is original and deep, but it does not force you to think differently. If a math giant from the past—someone like Gauss—were to come back to Earth, he would have a lot of catching up to do but he would find that math is done much the same way that it was done during his life.

Computer science, by contrast, is a new way of thinking, a new way of looking at things. For example, mathematics can’t come near to describing the complexity of human endeavors in the way that computer science can. To make a literary analogy, mathematics produces the equivalent of one-liners—equations that are pithy, insightful, brilliant. Computer science is more like a novel by Tolstoy: it is messy and infuriatingly complex. But that is exactly what makes it unique and appealing—computer algorithms are infinitely more capable of capturing nuances of complex reality in a way that pure mathematics cannot.

“Stepchild”! That one word says it all. There’s a whole Tolstoyan novel in it, or maybe a Henry James, or at least a Grimm Brothers fairy tale. Computer science is the poor relation, the orphan, the foundling—taken in by a grand family but never taken seriously, never allowed to forget its doubtful origins. Or else computer science is the arriviste, the rich American cousin with too much cash and too little taste, who tears down the mossy old manse and puts up a spiffy new house designed by Frank Gehry. Or do we have a tale of sibling rivalry—the two children with different visions of the future for the family firm, neither of whom can ever feel secure in the love of a cold and distant parent?

I don’t know how this tear-jerker will end. Without sectarian violence, I hope. In a sense it’s none of my business, since I’m not a member of either department. But I do have to say that the idea of being asked to choose between mathematics and computer science is preposterous. If I were pleading this case, I would emphasize the connections between those fields, not the distinctions.

Here’s an algorithm for finding the area of any simple polygon. First, assign an orientation to every edge by drawing an arrowhead pointing in the counterclockwise direction around the cycle of edges. After this labeling, each vertex of the polygon becomes the “tail” endpoint of one edge and the “head” endpoint of another. Now, for each edge, evaluate the following 2 × 2 determinant:

where x_t and y_t are the coordinates of the tail point and x_h and y_h are those of the head point. The determinant evaluates to x_ty_h – x_hy_t. The sum of all the determinants is twice the area of the polygon.

Question: Am I the only one who hasn’t always known about this algorithm? Did I pick the wrong day to skip school? I remember “one-half the base times the height” and various other fussy formulas for specific polygons, but I don’t believe I ever learned this method.

I belatedly got a clue from some excellent lecture notes (.ps.gz) by Jonathan Richard Shewchuk of the University of California at Berkeley. I gather that the algorithm is widely used in the computational-geometry community. Land surveyors also know it: I’ve found descriptions of what I think is essentially the same procedure in surveying manuals going back at least as far as 1808 (though without explicit mention of determinants). In 1986 Bart Braden of Northern Kentucky University wrote about the algorithm (and its extension to figures enclosed by continuous curves) for The College Mathematics Journal. So this isn’t really a new trick, and yet I have a sense it is not widely taught or employed. Or, again, maybe it’s just one of my personal blind spots.

In any case, I am grateful to know it now. It has a lot going for it:

• Generality. It offers one formula for any simple polygon (where “simple” means no self-intersections). The procedure is the same no matter what the number of edges, whether the polygon is regular or not, and whether it is convex or not.
• Robustness. The algorithm seems to be indifferent to many of the anomalies and degeneracies that plague lots of geometric methods. The position and orientation of the polygon on the plane are of no consequence mathematically (though they might affect numerical accuracy). Oddities such as zero-length edges cause no trouble. If you ask for the area of a polygon that’s been squashed flat, the procedure returns the sensible and correct answer of zero.
• Numerical niceness. The only arithmetical operations needed are multiplication, addition and subtraction, with just a single division by 2 at the end. There are no square roots, trig functions, or other sources of irrationality. Do the arithmetic exactly and you’ll get exact results.

What is the history of this method? Who discovered it? Does it have a name? Because it draws on concepts from coordinate geometry, I can’t see how the Greeks could have found it. What about Descartes and Fermat? Or did it have to wait for the full development of ideas about vectors, matrices and determinants?

Among the surveying manuals that mention the technique, this is the earliest I’ve found:

Flint, Abel. 1808. A System of Geometry and Trigonometry: together with a treatise on surveying: teaching various ways of taking the survey of a field; also to protract the same and find the area. Likewise, Rectangular Surveying; Or, an accurate method of calculating the area of any field arithmetically, without the necessity of plotting it. Second edition. Hartford: Oliver D. Cooke. (See pp. 59–94 on “rectangular surveying.”) [Google Books link.]

And this is the reference for Braden’s article, which among other things gives a proof of the algorithm’s correctness.

Braden, Bart. 1986. The surveyor’s area formula. The College Mathematics Journal 17(4):326–337.

Update: As soon as I posted the above, it occurred to me that the algorithm leads to an immediate proof that any polygon whose vertices lie on the lattice of integers must have for its area either an integer or a half-integer. This also follows from Pick’s Theorem (the point-counting method for finding the area of a lattice polygon). There’s a vast literature on Pick’s Theorem and lattice polygons, so maybe that’s a place to look for other discussions of this method.

Update 2007-02-04: A tipster has alerted me to another important reference: Gilbert Strang, “Polar Area is the Average of Strip Areas,” The American Mathematical Monthly, Vol. 100, No. 3. (Mar., 1993), pp. 250-254. There I find the following passage:

“Known but not well known,” says Strang. But evidently becoming better known, at least among Minnesota carpet layers.