Algorithms in the real world
Arik Jun 11
Computer scientists that need to write code for a living, constantly straddle the line between the beautiful and neat little world of theory and the somewhat messy, “macgyverish” world of practical software engineering.
In the theory world, cute cuddly objects pass messages of peace and love between each other. They live on a beautiful planet, replete with natural resources.
In the practical world, objects sometimes try to set each other on fire. They drunk drive, and they live in a 100 sq ft apartment with their wive’s mother who moved in after they got married to that hot method from that other project.
But all the same, computer scientists are always trying to bring some of those cute objects back with them from Theory planet whenever they go on a visit.
One time, even I got lucky. A large company I worked for needed a directory system to help customers navigate their city-block-size building. You know those You-Are-Here maps they have in the malls with a red big dot that tells where you are. So like that, but on big digital screens.
Anyhow, long story short the project manager predicted this project will take many weeks to complete due to the perceived complexity involved in routing customers from any point A in the building to any point B.
In fact I thought so myself too. But then I remembered our networking guy saying something about a “shortest path algorithm” a while back. At the time he was trying to explain to me how network packets travel in an efficient manner given several possible paths.
A simple Google search brought back a complete implementation of an algorithm called the Dijkstra’s algorithm. The whole thing, top to bottom must have been 100 lines of code in Java. Very concise.
Since I didn’t know a thing about how it works or what it’s trying to solve I pulled up the Wikipedia article:
Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph.
For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities.
Oh, okay. So all I have to do is model all the points in the building as “nodes”, link them using “edges” and assign a distance to every edge. Then the algorithm can use this information to figure out the shortest path from any point A to any point B. Sounds easy.
I copy pasted the code to my project, fed it a few sample points and tested it on pair of endpoints. It worked.
I tried it on a few more endpoints, added alternative paths for the algorithm to choose from and it worked flawlessly every time.
I deployed the code to our dev environment and showed it to the project manager. He couldn’t believe it. I was showing him a working demo of the product within days of receiving the assignment.
He then proceeded to test it himself. Certain he could find edge cases which would break the algorithm. He even came to me a few times proudly announcing that he found one. But in each and every case we found out that his input was at fault and not the algorithm.
So what’s the moral of the story? Well, for me at least, it was the realization that Computer Science is a useful subject and that it is a distinct activity from software building. Moreover, it taught me that there are powerful, fundamental principles to programming. And that it’s absolutely worth learning these fundamentals very well, because the time invested in learning them will pay itself back many times over.