Taking A Crack At The Traveling Salesman Problem

The human mind is a path-planning wizard. Think back to pre-lockdown days when we all ran multiple errands back to back across town. There was always a mental dance in the back of your head to make sense of how you planned the day. It might go something like “first to the bank, then to drop off the dry-cleaning. Since the post office is on the way to the grocery store, I’ll pop by and send that box that’s been sitting in the trunk for a week.”

This sort of mental gymnastics doesn’t come naturally to machines — it’s actually a famous problem in computer science known as the traveling salesman problem. While it is classified in the industry as an NP-hard problem in combinatorial optimization, a more succinct and understandable definition would be: given a list of destinations, what’s the best round-trip route that visits every location?

This summer brought news that the 44-year old record for solving the problem has been broken. Let’s take a look at why this is a hard problem, and how the research team from the University of Washington took a different approach to achieve the speed up.

Continue reading “Taking A Crack At The Traveling Salesman Problem”

Lewis Latimer Drafted The Future Of Electric Light

These days, we have LED light bulbs that will last a decade. But it wasn’t so long ago that incandescent lamps were all we had, and they burned out after several months. Thomas Edison’s early light bulbs used bamboo filaments that burned out very quickly. An inventor and draftsman named Lewis Latimer improved Edison’s filament by encasing it in cardboard, earning himself a patent the process.

Lewis had a hard early life, but he succeeded in spite of the odds and his lack of formal education. He was a respected draftsman who earned several patents and worked directly with Alexander Graham Bell and Thomas Edison. Although Lewis didn’t invent the light bulb, he definitely made it better and longer-lasting. Continue reading “Lewis Latimer Drafted The Future Of Electric Light”

Video: Exploring The Abandoned Birthplace Of The 6502 And Commodore 64

I miss my friend Dave DiOrio. He was a chip designer in the 1980’s, which made him one of the true wizards back then. We met my first day when I started at Commodore Business Machines, though my paycheck said MOS Technology on it.

MOS Technology was the birthplace of the venerable 6502 microprocessor, the VIC video chip, and the SID sound chip to name the really famous ones. It also brought us the TED Text Display chip, a whole boatload of Amiga chips, and several other chips that almost did what we wanted them to do.

I worked with magicians whose stock and trade were comprised of half-part quantum tunneling effect and half-part straight-up logic implementation. These magicians weren’t bound by the number of pins available for TTL logic, not like us lowly hardware engineers who had to string 14 and 16 pin chips together to do any real lifting.

Below the spartan offices where the designs were drawn lived the dragon otherwise known as a chip fab, short for integrated circuit fabrication plant. This beast ate sand and made wafers; slices of almost pure silicon in crystalline form with all kinds of intricate things craftily grown on top of them.

Memory Lane: Touring the Abandoned MOS Headquarters

MOS Technology was started in 1969 by Allen Bradley but only became the MOS that I think of when I talk about the good old days when Chuck Peddle and a bunch of cohorts from Motorola, including Bill Mensch, swept in and produced the 6502 microprocessor, which resembled a particular Motorola processor quite a bit, in fact a lot. Lawsuits followed.

Meanwhile the 6502 was taking over several industries as the go-to processor for everything from medical equipment to microwave ovens to home computers. It was while designing home computers that I met Dave while standing above a chip fab. I can still remember the smell of that dragon farting below our feet… its an understatement to say I miss those times.

A couple of years ago I had a chance to return to the old stomping ground as it were, and set foot (legally) inside of MOS headquarters in Norristown, PA — which had become CSG (Commodore Semiconductor Group) by the end. The basement was dirty and flooded and yet we found wafers, one from one of the computers I worked on.

The ground floor was dark and quiet, I stood at the dirty glass entrance doors looking out at a drab street and I quickly moved on before I got hit by some sort of self evident metaphor for life that would have been annoying.

The second floor was where our offices had been. The hot press of design deadlines has long since left this space, now all there is to see is the golf course out the window and a little camp fire someone had made. I got to show this video to Dave, including the view looking out his old office window, and we both smiled at the thought that it was now 35 years later.

Dave has since passed away, the world has one less wizard and as the video shows, the dragon has long since gone quiet.

AUTOVON: A Phone System Fit For The Military

It’s a common enough Hollywood trope that we’ve all probably seen it: the general, chest bespangled with medals and ribbons, gazes at a big screen swarming with the phosphor traces of incoming ICBMs, defeatedly picks up the phone and somberly intones, “Get me the president.” We’re left on the edge of our seats as we ponder what it must be like to have to deliver the bad news to the boss, knowing full well that his response will literally light the world on fire.

Scenes like that work because we suspect that real-life versions of it probably played out dozens of times during the Cold War, and likely once or twice since its official conclusion. Such scenes also play into our suspicion that military and political leaders have at their disposal technologies that are vastly superior to what’s available to consumers, chief among them being special communications networks that provide capabilities we could only have dreamed of back then.

As it turns out, the US military did indeed have different and better telephone capabilities during the Cold War than those enjoyed by their civilian counterparts. But as we shall see, the increased capabilities of the network that came to be known as AUTOVON didn’t come so much from better technology, but more from duplicating the existing public switched-telephone network and using good engineering principles, a lot of concrete, and a dash of paranoia to protect it.

Continue reading “AUTOVON: A Phone System Fit For The Military”

The Astronomical Grit Of Ronald McNair

There is more than one way to lead a successful life. Some people have all the opportunity in the world laid out before them, and it never does them any good. Others have little more than the determination and desire they’ve dredged up within themselves, and that grit turns out to be the abrasive that smooths the path ahead.

Ronald McNair succeeded despite poverty, racism, and an education system designed to keep Black people down. He became an accidental revolutionary at the age of nine, when he broke the color barrier in his small South Carolina town via the public library. This act of defiance in pursuit of education would set the course for his relatively short but full life, which culminated in his career as a Space Shuttle mission specialist.

Rule-Breaker with a Slide Rule

Ronald McNair was born October 21, 1950 in Lake City, South Carolina, the second of three sons, to Pearl and Carl McNair. His mother was a teacher, and encouraged his love of reading. Ronald’s father, Carl was an auto mechanic who never finished high school and always regretted it. Though the family was poor, Ron grew up surrounded by books, music, and support.

Continue reading “The Astronomical Grit Of Ronald McNair”

Start Me Up: What Has The Windows 95 Desktop Given Us 25 Years Later?

We’ve had something of an anniversary of late, and it’s one that will no doubt elicit a variety of reactions from our community. It’s now 25 years ago that Windows 95 was launched, the operating system that gave the majority of 1990s PC users their first taste of a desktop-based GUI and a 32-bit operating system.

To the strains of the Rolling Stones’ Start me up, Microsoft execs including Bill Gates himself jubilantly danced on stage at the launch of what was probably to become the company’s defining product, perhaps oblivious to the line “You make a grown man cry” which maybe unwittingly strayed close to the user experience when faced with some of the software’s shortcomings.

Its security may seem laughable by the standards of today and the uneasy marriage of 16-bit DOS underpinning a 32-bit Windows operating system was clunky even in its heyday, but perhaps now is the best time to evaluate it unclouded by technical prejudice. What can we see of Windows 95 in the operating systems we use today, and thus from that can we ask the question: What did Windows 95 get right? Continue reading “Start Me Up: What Has The Windows 95 Desktop Given Us 25 Years Later?”

A Tale Of Tutor Texts

Have you ever had one of those books that let you choose your own adventure? You know, the book will say “The bully tells you to hand over the secret message. If you want to run away, turn to page 48. If you want to fight him, turn to page 70.” While this is normally a staple of children’s literature, there were a series of training books known as Tutor Texts that used the format to teach technical topics.

In fact, one of these books was my first introduction to computer programming more years ago than I care to admit. But it wasn’t just computer programming. There were titles from the same publisher about trigonometry, slide rules, and even how to play bridge. I own four of these old books and it got me to thinking about how we deliver information on the web. Maybe these books were ahead of their time.

Continue reading “A Tale Of Tutor Texts”