Bill Cook sent me a file yesterday that renders the Endeavour photo on my blog as the solution to a 66,290-city Traveling Salesman problem. His iPhone app Concord TSP chose 66,290 points and then solved for the shortest path connecting these points, a feat that would have strained a supercomputer a few years ago. (Bill Cook and I are not related as far as I know.)

Here is a thumbnail image of the full TSP tour:

You can find the full PDF here (1.24 MB). To show some of the detail, here is a close-up from near the top-left corner of the image:

I asked how the tour was constructed:

How do you construct a set of points whose TSP solution resembles a photograph? Is it sufficient to add more “cities” in regions where you want darker shading? And are the cities added at random with a density specified by color depth?

Bill Cook replied:

By default, the app will select the points along the line you describe: it splits the image into a grid, computes the average gray scale in each grid region, and drops a number of random cities into each grid region in proportion to the square of the average gray scale. This technique was first proposed by Bob Bosch and Adrianne Herman at Oberlin College. It is the default since it takes almost no time to compute, but I include two other options, that each take about a minute to render a large image on an iPhone 4.

The image of The Endeavour was created with a method Jim Bumgarnder proposed in his Stipple Cam project.

Related post:

Moore’s law squared

As the iPad descends upon us, it is fair to ask, "Is this the beginning of the end, or the end of the beginning?" Depending upon whom you ask, the conclusions vary widely. The yin and yang of openness vs. integrated raises a fundamental question that underscores the battle being fought in the simmering industry battle between Apple and Google.

As the iPad descends upon us, it is fair to ask, "Is this the beginning of the end, or the end of the beginning?" Depending upon whom you ask, the conclusions widely vary.

For example, RealNetworks' Rob Glaser forcefully argues that Apple's vertically integrated model "Must be stopped." He cautions: "If that's the way the industry plays out -- and there are a couple of vertical stovepipes that are closed -- A: we will have a much slower pace of innovation than we've ever had and B: there will be a tremendous loss in terms of value creation versus it being more horizontal."

Meanwhile, science fiction writer, blogger and tech activist, Cory Doctorow, recently made waves when he asserted in Why I won't buy an iPad (and think you shouldn't, either) that, "If you can't open it, you don't own it. Screws not glue." He concluded:

The real issue isn't the capabilities of the piece of plastic you unwrap today, but the technical and social infrastructure that accompanies it. If you want to live in the creative universe where anyone with a cool idea can make it and give it to you to run on your hardware, the iPad isn't for you. If you want to live in the fair world where you get to keep (or give away) the stuff you buy, the iPad isn't for you. If you want to write code for a platform where the only thing that determines whether you're going to succeed with it is whether your audience loves it, the iPad isn't for you.

And don't even get me started on the legions who dismiss Apple's end-to-end approach with an "Apple's Evil" slap, or more stridently, paint the story as "destined" to play out as things did in the PC Wars, with arrogant Apple racing to an early lead, only to get its head handed to it in the end.

I won't spend a lot of time bringing to the fore the masses that see the Apple model in more favorable terms, as the numbers speak for themselves across just about any metric that matters:

85 million iPhones/iPod Touches/iPads sold
185,000 applications built
100,000 developer ecosystem
4 billion application downloads
15 billion iTunes media sold
JD Power Award for Customer Satisfaction
Ungodly operating margins/cash flow

So how to reconcile the animus with the market's clear directional momentum? Read on ...

Progress and grumpy old men

The late Herb Caen, the legendary columnist of the San Francisco Chronicle, once wrote a piece about the worsening state of San Francisco and, in particular, one of its main arteries, Market Street.

In it, he lamented about how this thoroughfare was always under construction, how the city's charms and enduring traditions were getting swept aside by outsiders, and how the place was becoming less and less hospitable to locals and long-timers, forcing Caen to wonder if, perhaps, San Francisco's best days were behind it.

Ah, but Caen was setting us up for an unexpected upper-cut, as at the tail end of the piece, he reveals (I am paraphrasing), "Would it surprise you to know that I wrote this piece way back in 1954?"

Caen's point was that then, as now, every generation sees their generation as the Real Generation and the Right Approach, when in truth, progress just moves forward.


Hence, the locals of San Francisco, circa 1954, saw a city losing sight of its traditions and therefore, its magic. In truth, the city was just moving forward with the times.


Thus, it was unsurprising that 30 years later, today's locals would reach the exact same conclusions about the "good old days" being their particular generational approach.

I would argue that Glaser, Doctorow and a number of others (Daring Fireball's John Gruber covers some of the other disenchanted in an excellent piece, The Kids Are All Right) are simply guilty of confusing their truth with The Truth, a not so subtle way of saying, "My Way or the Highway."

A note aside, while I have heard plenty of grumpy old men lamenting about the continuing rise of the Apple approach and its dark implications, I have yet to hear a single female prognosticator confuse such attributes with real-world unfavorable outcomes. Perhaps, it's because women don't long for the "good old days" of Stone Age tools, techno-babble, impersonal computing and the like.

Me personally, my first computer was a TRS-80, so I understand the nostalgia of being able to tinker down to schematics and assembly code, and just the same, prefer the ability to apply my muscles judiciously to higher level problems versus lower level ones.

Hence, what I give up in terms of absolute flexibility, I gain in not having to worry about hardware abstractions, infinite form-factors, middleware, glue code, software distribution, marketplace and monetization.

To me, that is a more than acceptable trade-off, inasmuch as you would be hard-pressed to argue that the model is less democratic or even less web friendly (while Apple is clearly trying to create the best native experience possible, they have unquestionably also created the best mobile web experience and are key proponents of HTML5 and pioneered WebKit adoption).

Nonetheless, the yin and yang of openness vs. integrated raises a fundamental question that underscores the battle being fought in the simmering industry battle between Apple and Google.

Do we really need more inmates?

There are two bookends that gave me a grammar and narrative for thinking about software (and hardware) development and design. The first is "The Mythical Man-Month" by Fred Brooks, and the second is "The Inmates are Running the Asylum" by Alan Cooper.

In "Inmates," Cooper makes the argument that too often the development process is driven by techies building the types of products that they would like to use, as opposed to really understanding the aspirations and outcome goals of their target user, let alone who that target user even is.

Worse, they often compensate for this blind spot by building products that address all use cases, including edge cases, and build a design interaction model that is a composite of that blob of functionality.

The end-result are products that are confusing, needlessly complex and that address all theoretical problems from a check box perspective, but few real problems from a specific outcome perspective.

Keep this in mind next time you are comparing the Apple product that seems to be "missing" certain features relative to the cheaper alternative on the other shelf. Nothing is free when it comes to product design decisions.

Margins, and who keeps which piece of what dollar

It's worth revisiting Rob Glaser's earlier comment about "stopping Apple," as it underscores the real reason many want to stop Apple.

Back in the days of the PC, the rise of Microsoft and Intel led to a horizontally organized industry. Microsoft and Intel kept the highest margin dollars for themselves, and could expand into adjacent segments as they saw fit. They also left a number of chunks of the hardware, software and infrastructure stack to third parties.

This type of loose-coupling worked because the PC was essentially a homogeneous platform, and the expectations of user experience were such that daily system crashes, recurrent performance lags and numbingly-complex "enterprise" software was considered the rule, and not the exception.

Now, of course, the two industry standard-bearers of the Post-PC Era, Apple and Google, respectively, have addressed the challenges of old very differently. Google, by embracing simpler, loosely coupled (read: horizontally-focused) cloud-facing solutions, and Apple, by embracing vertically-integrated, complete product solutions that marry hardware, software, service, developer and marketplace.

But make no bones about it; the real tempest here is who keeps the high margin dollars.

In the case of Google, they are happy to allow any and all to plug into their search and advertising gravy train, so long as they can disrupt any and all incumbent segments ripe to be broken up by their model.

In the case of Apple, they see user experience and control of same as central to their value proposition and "govern" accordingly.

Whether you see one as more open, closed, virtuous or evil depends upon your personal preference about user experience and choice, not to mention your particular economic self-interest.


But that is a post for another time.

Related:

Innovation, Inevitability and Why R&D is So Hard
The Chess Masters: Apple v. Google
Open "ish": The meaning of open, according to Google
Android vs. iPhone: Why Openness May Not Be Best
iPad First Impressions: The Good, the Not So Good and the Not Yet

This is my contribution to Ada Lovelace Day

Ada Lovelace is, perhaps, the world’s first programmer of an actual computer. Others wrote about algorithms much earlier—think Euclid and the famous GCD algorithm—but she wrote a program for a specific computing machine. The machine was Charles Babbage’s Analytic Engine, and her notes look like a program to most.

Today I plan on joining over a million other bloggers in discussing women in science, and more specifically computing. The event is named after Ada Lovelace, and is happening all over the web.

Okay, I exaggerated about the number of bloggers, it is closer to 100,000 than a million—actually it is closer to 1,700. The number is not important; what is important is: we need more women administrators, educators, and researchers in all areas of computing. Further, more women who already have done great work in computing need to be recognized and given the awards and accolades they deserve. This has not always happened.

I am honored to be a tiny part of this special day, and I hope I can help in some way to make the event a success.

What To Do?

I am honestly unsure what I should do. For starters I am not a woman, and cannot really understand their issues. But, I have been in the computing field for over thirty years and perhaps I can add some small insights. I will try.

When I was first at Princeton we worked very hard to hire Andrea LaPaugh from MIT, where she got her Ph.D. We were successful, and for quite a while she was the only woman in all of engineering at Princeton. Later, she been the first tenured woman in engineering at Princeton. The balance is not perfect now, but I am happy to say today she is not the only tenured professor in engineering.

One day I was talking with a colleague from another engineering department. He asked me, “How many women did we have in Computer Science?” I immediately answered one—Andrea. Then, I asked the obvious question, “How many do you have in your department?” My colleague thought a long time—I guessed he must be adding up women faculty. Finally he said, “None.”

I am telling this story to show how subtle the issues can be concerning women in science. I gave him a very hard time: I said, you can take a long time to add up the cardinality of a big set, but you cannot take any time to figure out the cardinality of the empty-set. What was he thinking?

The Two Rule

One rule is the two rule. I learned this rule from my wife, Judith Norback, who is a Ph.D in psychology from Princeton. Often in an attempt to create balance—especially in academia—one woman will be placed on each committee. A woman. One. It is good to have women on committees, but putting one on does not usually work well.

The difficulty is a lone person on any committee is hard pressed to speak out and really make a difference. A lone person of any minority—the principle is the same for other minorities—is not in general the right choice. There are exceptions to this rule, but studies show one person, from a minority, is not nearly as effective as two. This is the rule of two. If possible always place two women on a group or a committee. They will be immensely more effective, if there are two.

Of course in order to make this happen the academic organization needs to have at least two women—another argument for more diversity. I do not claim to completely understand the reason the “two rule” works, but it does. Try it.

The Out Rule

Another rule is the out rule. This I learned from long experience watching fellow computer scientists operate—especially in academia. In the old days when wagon trains were attacked, they were taught to “circle the wagons.” In computer science we still do this, as do most other areas of science and academia.

However, in computer science the joke—unfortunately all too true—is we shoot the wrong way. We shoot in, not out. Hence, the rule of out: when attacked remember to shoot out, not in toward each other.

With all due respect, I have long noticed women on various committees often ignore this simple rule. They shoot in toward their fellow women. I have been on many committees of all kinds—award, hiring, program, and other types—and have noticed the women on the committee are often the hardest on women candidates. I have often argued for a women candidate for something, and noticed the other faculty were generally supportive. However, the women faculty in the room would frequently agree with me on the big points, yet attack the candidate on some minor points. Do not shoot in, shoot out.

I am not arguing for a decrease in standards. Never. I am arguing for both male and female faculty to be sure they are as objective as possible. I certainly am far from perfect, but I do think more attention should be paid to being aware of the out rule.

The Zero Rule

I am trying to be constructive and not writing a “moral with a tale,” but one last rule is critical in my mind. The zero rule is just this: there must be zero—no—tolerance for any jokes, comments, stories, of any kind that put down women. I have heard many of them over the years, and have always immediately complained about them. I believe such statements cause many women to go into other areas of science. We must be intolerant of any comments of this kind.

Ada As The First Programmer

It seems to me clear Lady Lovelace was more than the first programmer: she had great insight into what a computing device could or could not do. Here is a direct quote from her—it could have been written the other day. It would be interesting to see what she would think about computing today—she wrote this in 1842.

It is desirable to guard against the possibility of exaggerated ideas that might arise as to the powers of the Analytical Engine. In considering any new subject, there is frequently a tendency, first, to overrate what we find to be already interesting or remarkable; and, secondly, by a sort of natural reaction, to undervalue the true state of the case, when we do discover that our notions have surpassed those that were really tenable.

The Analytical Engine has no pretensions whatever to originate anything. It can do whatever we know how to order it to perform. It can follow analysis; but it has no power of anticipating any analytical relations or truths. Its province is to assist us in making available what we are already acquainted with. This it is calculated to effect primarily and chiefly of course, through its executive faculties; but it is likely to exert an indirect and reciprocal influence on science itself in another manner. For, in so distributing and combining the truths and the formula of analysis, that they may become most easily and rapidly amenable to the mechanical combinations of the engine, the relations and the nature of many subjects in that science are necessarily thrown into new lights, and more profoundly investigated. This is a decidedly indirect, and a somewhat speculative, consequence of such an invention. It is however pretty evident, on general principles, that in devising for mathematical truths a new form in which to record and throw themselves out for actual use, views are likely to be induced, which should again react on the more theoretical phase of the subject. There are in all extensions of human power, or additions to human knowledge, various collateral influences, besides the main and primary object attained.

To really appreciate her brilliant mind, read all her comments here. This is the front piece to the document:

Open Problems

The main open problem is continue to try and increase the number of women in all aspects of science, especially computing. I think there are already many good ideas on how to do this—perhaps what we need is to execute the best of these ideas. In any event have a happy Ada Lovelace Day. It would have been a great privilege to have met her.