Thomas Cormen:
"I’ll tell you a little story. A true story.
"I’ll tell you a little story. A true story.
In the late 1970s and early 1980s, I worked at a startup that made systems for computer-aided design. Users could define parts and store them in a library of parts. Each part could include another part by reference, so that if you changed the definition of a part, then all of its uses would update automatically. Part A could include a reference to part B, which could include a reference to part C, and so on. Circular references were not allowed, as a part could not include itself.
We had a customer that wanted the library of parts written out to tape so that each part appeared on the tape before any other part that used it. I was the only person at the company who knew that what this customer wanted was a topological sort of a directed acyclic graph. I knew that there was an efficient algorithm for this problem, and I knew where I’d seen it (in Knuth). I didn’t remember the details of the algorithm, and so I went to the library, got a copy of Knuth, and implemented the algorithm.
People at the company thought I was a god for knowing how to solve the problem, and how to solve it efficiently.
That’s why you want to know about algorithms."
No comments:
Post a Comment