Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
7  
Someone who has done UI for 20 years will probably have hard time finding a solution to a problem from another domain, in a short amount of time. –  Coder Aug 26 '11 at 13:11
37  
Spending a lot of time on the SE sites gives everyone a crisis of confidence I think! (Not that that's a bad thing). Happiness in life is finding the perfect balance between acceptance of what is and the desire to change it. –  TrojanName Aug 26 '11 at 13:35
2  
I could not reinvent it myself, but I try to remember how it works. make sure you understand this animation: upload.wikimedia.org/wikipedia/commons/2/23/… –  Job Aug 26 '11 at 23:00
6  
@Brian Tragedy of the local genius. You can hardly ever be the best at anything anymore. –  Rei Miyasaka Aug 27 '11 at 12:31
6  
a good computer scientist should but not necessarily a computer programmer or software engineer –  bye Aug 27 '11 at 19:36
show 4 more comments

11 Answers

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'

share|improve this answer
22  
@Nakilon - Programmers who ignore existing solutions are just wasting their time, and if they're not wasting their time, they're making a worse solution. See: Everyone making their own password hashing scheme vs bcrypt. –  Brendan Long Aug 26 '11 at 18:10
7  
@GSto: according to wikipedia, Dijkstra came up with the algorithm in less than an hour: 20 minutes, acording to first note on wikipedia: en.wikipedia.org/wiki/Dijkstra%27s_algorithm –  woliveirajr Aug 26 '11 at 18:18
7  
It's a relative simple algorithm, but Dijkstra was very talented, and had been trained in theoretical physics and advanced mathematics. There's nothing like a few years writing proofs to improve one's ability to design algorithms. –  kevin cline Aug 26 '11 at 18:53
15  
@woliveirajr - Well, I'm sure Newton took the same amount of time to come up with the laws of motion. After thinking about it for 20 years first. –  Rook Aug 26 '11 at 23:27
4  
@Nakilon - Yes that's why everyone writes everything in C, because otherwise you're just a coder, using someone else's high-level language. Oh wait, I mean assembly, otherwise you're just using someone else's low-level language. Oh wait, I mean flipping switches to change electrical circuits, otherwise you're just using someone else's instruction set. Or you know, you could just use what's already there and work on creating something new. Why waste time re-inventing Dijkstra's algorithm when you can invent something new, like a program that uses it? –  Brendan Long Aug 27 '11 at 6:38
show 9 more comments

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.)

share|improve this answer
55  
Don't worry, if brute force isn't working, you're just not using enough of it. –  Robbie Aug 26 '11 at 13:11
2  
+1 for hilighting the difference between theoretical CS and programming. Programming is real-world problem solving, and theoretical CS is there to support programming. However theoretical CS is not 100% essential in most peoples' everyday programming. –  Phil Aug 26 '11 at 21:21
add comment

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.

share|improve this answer
1  
BlackJack, I had to join this forum to point out that Bentley did not say what you claimed he said: Knuth said it, and Bentley quoted him. When I read your comment I thought you made a good point, but I like to verify my sources and had never heard of Bentley. I have, however, heard of Knuth and can trust what he says. Please check your sources better next time. –  Richard Aug 26 '11 at 16:49
8  
@Richard - The comment was "In Programming Pearls, Bentley says.." Knuth was the first to say it, but my source is Programming Pearls, not TAoCP, so I wrote what Bentley wrote. I did not claim that Bentley is the originator - I merely quoted what is said in the book. A great deal of material in books was not invented by the authors themselves, so I don't see why you would see it that way. –  BlackJack Aug 26 '11 at 17:10
    
By attributing the quote solely to Bentley you fail to due Knuth credit and, if "Bentley's" statement was wrong, you put Bentley in the position of having produced incorrect information, rather than merely having spread it. Strictly speaking, you didn't say what Bentley said: if you had, you would have said, "Bentley said that Knuth said that...". The quote is well-used here, but it is taken out of the context in which it was said. –  Richard Aug 28 '11 at 0:48
3  
@Richard - The quote I have listed is directly from the blog, which quotes directly from the book (literally, I think it's page 57 of the first edition). If you have this much issue with the statement, then contact the author of the blog and have him change it. –  BlackJack Aug 28 '11 at 1:13
1  
@Richard and BlackJack: You are both correct, but the attribution to the original author adds credence and context to the statement. My edit should be sufficient. –  Steve Evers Sep 5 '11 at 21:17
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Oh the irony...now that I can comment anywhere, should I delete the answer that earned me that privilege? There ought to be a badge for that. –  Keith Layne Aug 27 '11 at 20:51
    
There is - Disciplined however, if your reputation gets recalculated you'll be back down to 1. –  ChrisF Aug 27 '11 at 21:17
    
Yes, that's exactly my point...I would be going above and beyond discipline at that point IMO. If I converted my answer to a comment before deletion, I could have it all...I suggest a new badge called UberDisciplined for any deletion that causes you to return to brand new user status. :) –  Keith Layne Aug 27 '11 at 21:22
add comment

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.

share|improve this answer
add comment

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.)

share|improve this answer
3  
I agree that yes, a competent programmer should be able to come up with bubble sort or its equivalent. It might even be a productive use of time to actually implement it and try it out, perhaps just to understand the problem better. But I think it needs to be said that no competent programmer would then go on and actually use it in production code. Doing that is what makes your customers come back next year and complain that, now that they have more data to process, your O(n!) algorithm will take twice the age of the universe to complete... –  Thomas Padron-McCarthy Aug 27 '11 at 8:36
    
Who cares if you can invent algorithms, if you can't even recognize when it sucks? Self-criticism is as important for a programmer as creativity. I'd rather work with a programmer that's quick to admit when they know their own solution is taking too long or is unlikely to be the best, than with a programmer who wants to reinvent every wheel because it bruises their ego to do otherwise. –  Rei Miyasaka Aug 27 '11 at 12:22
    
I do agree on both points, but I think we are measuring two different things. One is the ability for the programmer to solve problems (something I consider essential). Other is self-criticism (I do consider this essential but not for programming: for life) and the ability to judge code (highly desirable). I also would say that solutions that take forever are not really solutions, are they? ;) –  Alpha Aug 29 '11 at 23:25
add comment

Do Not Worry

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:

  1. I do not recommend reinventing the wheel but when you do...
  2. Try not to completely reinvent it and...
  3. Do not worry if you cannot do it. That's why we have a programming community :-).
share|improve this answer
add comment

Yes, he/she should.

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Cryptographic algorithms are easy to verify an implementation of; known correct test vectors are a dime a dozen for any publicly specified algorithm, and it's either correct or not. (You may get suboptimal performance with a custom implementation, but if it's only correct, that can be worked on.) The hard part in cryptography is things like random number generation, proper handling of raw keys and key expansion tables in-memory, proper handling of user inputs (salting, etc.), storing something to allow you to figure out if the decrypted data is valid, and so on. –  Michael Kjörling Aug 27 '11 at 19:14
    
I was thinking more along the lines of timing attacks etc, stuff almost no programmer knows about. It's not always an issue, but an important one nonetheless. Also, combining cryptographic primitives usually doesn't work like one expects, this is also a hard part of security. –  Alex ten Brink Aug 28 '11 at 15:43
    
While timing attacks etc is certainly a valid concern (and not only in cryptography), I'd argue that an implementation's susceptibility to such has no impact on its correctness. And there are many, many ways to foul up in cryptography way more than just enabling timing attacks. Bruce Schneier used to run his Doghouse series; I haven't seen anything in it recently, but there are plenty of cautionary examples there. google.com/search?q=site%3Aschneier.com+%22the+doghouse%22 –  Michael Kjörling Aug 29 '11 at 8:52
add comment

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.