Share On Twitter Facebook Google+ LinkedIn Pinterest Tumblr Reddit
Question

Working as a programmer, is it useful to study by heart standard algorithms such as Dijkstra, Quicksort and so on, or do you just Google them and use them?

Tags: Quicksort Dijkstra algorithms
Date:
Status:Unresolved
Question Id:67

I apologize for not reading through the other 17 answers before writing mine. I’ll address the two algorithms mentioned in the question: Dijkstra’s algorithm and quicksort.

You need to know the conditions under which you will be running the algorithms.

For Dijkstra, you want to be sure that all the edge weights are nonnegative. A single negative edge weight can produce incorrect results. OK, now that you’ve verified that all the edge weights are nonnegative, what else do you know about them? Are they all equal? Then you can just run breadth-first search instead. Are they all integers in a constrained range? Then you can run Dial’s algorithm, which is really just Dijkstra’s algorithm with a bucket-based min-priority queue.

For quicksort, what do you know about the keys that you’re sorting? Are they all integers in a constrained range? Then maybe you’re better off with counting sort or radix sort. Is the array almost sorted, in the sense that every item is close to where it belongs in the sorted order? Then you might be better off with insertion sort.

You don’t necessarily need to be able to regurgitate the code for any particular algorithm or data structure—yeah, go look it up in CLRS or another source—but you need to know when to apply it. To give an analogy to the tools that I have down in my basement workshop, if I really want to, I can drive a nail with a screwdriver. But that doesn’t mean it’s the best way to do so.

Answer
Date:
Correct:No

A single negative edge weight can produce incorrect results. — …unless you modify the algorithm to reinsert vertices into the priority queue when their distance values decrease (and to notice negative cycles), in which case a single negative edge only doubles the running time in the worst case (and usually has even less impact in practice).

Answer
Date:
Correct:No

I’d argue that a significant portion of programmers never necessarily come across a use case, where some built in sort function wouldn’t be enough, but they need to realize it when they come across one. I’d say more generally:

You need to roughly know what algorithms exist and to be able to (re)learn and understand the conditions under which you should be running the algorithms.

Answer
Date:
Correct:No

I wonder if there is a database that lists these preconditions for algorithms?

Answer
Date:
Correct:No

Ask an old programmer who's been bitten on the rump by the wrong one.

This is definitely one of those ‘ask a friend’ type things. They can glance at it and give you the answer in seconds.

Next, this is where resources like Stack Overflow shine. Not you asking the question, necessarily, but when you search it'll start with the broadest case and your narrowing it down will teach you the important key concepts to select with.

And that's the problem with a normal database for a problem like this. You need to know how to ask the question, which often leads you right to it on SO or describing it to someone.

Heck, ask your cat, dog or significant other as a last gasp effort. In an interview, ask your interviewer if you're totally lost. It may not win you that specific job, but chances are you'll learn more stuff for the next interview.

Oh, and how us ‘old dudes’ do it? Years of experience with the ‘shape’ of solutions. You develop a feel for where systems break and know to look out for edge cases, literally and figuratively.

Take your search paradigm. If you're searching for lowest weighted path, simplest is root to leaf on a tree, all positive integer lengths. Then you keep adding constraints until your problem looks like an algorithm. That is, you're doing a parallel search between the graph and algorithm characteristics.

And that construct develops over time. I can't give you ‘use x algorithm for y problem’ by name, but I could find it in minutes with a copy of CLRS just using the above model. That is, I know where to start looking and then where to dig once I have the right area.

Your Answer

Review Your Answer