I'm suffering a crisis of confidence in my ability as a computer programmer.
Yesterday I tried to come up with my own shortest path algorithm for a graph and after some hours I simply threw in the towel and learned Dijkstra's algorithm.
Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?
Oh well, at least I was able to reinvent bubble sort :D
A good programmer should realize that a great algorithm has already been written to solve a problem and doesn't waste time re-inventing wheels.
I doubt Dijkstra came up with the shortest path algorithm in a few hours, so that seems like a really high standard to use for determining if someone is a 'good programmer'
Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?
First, you are perhaps confusing programming with theoretical computer science. A fantastic programmer needs a good fundament in computer science but he doesn’t need to be fantastic. Dijkstra was fantastic at computer science.
Secondly, I would expect anybody with a sound understanding of graphs to develop their own graph traversal after a bit of thought. But not a shortest path algorithm. Dijkstra’s algorithm in particular is highly sophisticated. Once you understand it, it’s blindingly obvious. But most things are that way.
You could probably derive some kind of shortest path algorithm after trying out some stuff and giving the idea some time. But don’t be disappointed if that takes hours, or even a few days. This is completely OK and normal.
(Caveat: well, you should be able to brute force the problem in a few hours tops, but this wouldn’t yield a working algorithm even on fairly small graphs.)
Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?
Definitely unrealistic. People don't just "come up" with algorithms in a few hours. It takes a lot of effort and work. To quote this blog:
In Programming Pearls, Bentley, quoting Donald Knuth, says "While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962."
and Bentley's version was also problematic when implemented for large sets.
Furthermore, a good programmer knows what tools are at his disposal and when to use those tools. You don't get extra points for originality or doing things differently - you want it to work and work well.
It's very much unlikely that you will be able to find a better solution than the ones you can choose from.
Coming out with a better algorithm than one considered "the best" (in your case, the shortest) is no something everyone can do. Probably it's not even possible.
A good programmer should be able to understand the logic behind the algorithm, and why it's better or worse (or simply inadequate for that particular problem) than other algorithms which try to solve the same problem.
(s)He should be also able to know if it's really the best way to go for solving that particular problem.
Anyway if you want to practice, you can still try to write your personal implementation of an algorithm, trying to solve a problem using your mind. It may not be the best, but it's a good practice for problem solving.
This reminds me of something I read about the difference between "software engineering" (what I would call programming) and the other engineering disciplines. Come to think of it, I think it was the original Design Patterns book. I'm sure someone here can quote it off the top of his head.
Anyway, the point (although not exactly geared toward algorithm design) was that the engineering disciplines are codified; no civil engineers are likely to spend time trying to reinvent the I-beam, but programmers do it all the time. The problem (and I realize that I am merely echoing the sentiments of many) is that this behavior is wasteful and error-prone, and serves the ego more than the solution.
Computer science led me to programming, and I love both. However, I am a much better programmer than computer scientist. I would never accuse you of being incompetent because you couldn't reinvent Dijkstra's algorithm in an afternoon. I would question your competence as a programmer if you couldn't recognize a problem that could be solved via a shortest-path graph algorithm.
That said, I believe that thinking about algorithms and trying to design and implement new ones is (potentially) fun and (almost) always instructive. I just try to cleanly separate my CS time from my programming time. For programmers, our (especially paid) time is better spent solving practical problems instead of asbtract ones. Besides, CS time almost always crushes my confidence.
You're not going to notice the same things that everyone else does. I think that's just a fact of life that we have to live with. Much of it comes down to your passive learning and the mental models that you've developed as a result of them.
I know some very intelligent and competent programmers who had to be taught DeMorgan's law at school before they could do it consistently. I happened to figure out Dijkstra's Algorithm on my own (and I have to admit I'm a bit proud of it), but it took me a really long time until I could even understand bubble sort.
More famously, Einstein, who you'd think would be an expert in knot theory, couldn't tie his own shoelaces until he was around ten years old.
Chances are good that you've unknowingly reinvented many things that many others would have never figured out had it not been for them being taught explicitly.
I beg to differ for what most of the answers say. While I wouldn't expect a programmer of any level to be able to come up by himself on Dijkstra's algorithm, I definitely would expect him to come up with any way (efficient or not) to solve the problem.
For example, you said as a side comment that you were able to come up with bubble sort on your own. I know its the stinkiest of sorting algorithms, but you found a way to solve a problem, and that's what I do expect programmers to be able to: find a way to solve problems.
Of course, investigating and finding solutions done by others also work, but the extreme of that point is a guy that does not think of himself and whose programs are a compendium of Google searches.
I think I'm sounding harsher than I actually want to, but my point is: I would expect a programmer to be creative enough to come up with a solution to a problem, even if the solution is buggy or messy.
So, coming back to your case, I don't think you should have to come up with Dijkstra's algorithm, but if you have the ability to write an algorithm to try out several possibilities and find the shortest path without ending on a infinite loop, then you've got my approval.
(BTW my approval counts in the same order of importance as a free car wash coupon.)
It might be the moral equivalent of bubble sort, but I do think a good programmer should be able to come up with at least something that works, however inefficient it might be.
Needless to say, if that particular problem would come up a good programmer would first look if there is a library to do that for him, or which published algorithms do that and are easy to implement.
Of course, many programming tasks are much less difficult and not everybody needs to be able to tackle such hard problems. But you'll want to have someone with a mind like that on your team, because you might have some complicated project specific problems where you can't rely on loads of previous scientific research.
As a Perl Programmer, I am all about never reinventing the wheel. That is the job of CPAN. If there is a simple, well supported algorithm or module, we use it. If there isn't a good module, then we invent the wheel. That is one of the greatest things about Perl.
So what I am saying is this:
Graph theory, and the algorithms that apply to it, look simple on the surface but are generally far from it. You'd think the formation of non-crossing (planar) graphs is simple, for instance, at first glance. Last year I looked extensively into this problem (planarity via elimination of Kuratowski subgraphs). I can tell you, from that experience, that the people who write these algorithms typically spend the duration of their PhD studies doing so, and sometimes that research is done in teams. And as researchers, that is their sole working focus over that period of time. It isn't sensible to think that we on-the-ground engineers can expect the same. As someone else here rightly said, its blindingly obvious once the solution is in front of you. That always seems to be the case!
Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?
I'd go as far as to say that if you're able to invent an algorithm for a well-known problem like Shortest Path all on your own, you're being a bad programmer.
It'd mean you're ignoring quite a history on the Shortest Path problem, going from a O(|V|^4) algoritm published in 1955 to the O(E + V log V) algorithm published in 1984 (which is Dijkstra's algorithm with Fibonacci trees). You're almost guaranteed to do worse than the algorithms already devised. Worse still, there's a good chance your algorithm has gaps or errors making it incorrect. In addition, you'll almost surely spend a lot more time thinking up your algorithm, implementing it and testing it than the time it'd take to re-use an existing algorithm.
Leave the design of algorithms to the algorithms designers. Programmers are consumers of their results. Programmers combine algorithms and put them to work on real-world tasks. A police officer need not be able to reinvent the law to be able to work, or to be a good officer.
I even encourage you to use implementations made by experts rather than implementing the algorithms yourself for any moderately complicated algorithm. It's more likely to be correct, chances are they made it faster than you ever will and it saves you a lot of time. This is particularly true for cryptographic algorithms, because you get the additional demand of security, which usually only experts can provide you.
