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.

This question already has an answer here:

I am a Computer Science student pursuing my Master's degree with my eyes toward gaining employment in the field of software development. I have always enjoyed the study of algorithms, and I've been repeatedly hearing from colleagues and mentors about the importance of a good understanding of algorithms. So I have decided to begin studying algorithms in earnest.

As I began my study of algorithms I came to discover that there are, generally, three areas one can concentrate on:

  1. studying the design of an algorithms: e.g. learning an efficient sorting algorithm

  2. learning to prove the correctness of algorithms: e.g. I've come up with an algorithm to handle a certain problem. Intuitively, I believe it works, but what about proving that it, in fact, does what I expect it to do.

  3. algorithm analysis: given an algorithm, determine the efficiency of the algorithm by calculating the running-time required by the algorithm.

Which of the above do you think is the most vital area to focus on? Given your answer, do you have a book to recommend that you think comes closest to meeting that objective?

Thank you.

share|improve this question
add comment

marked as duplicate by gnat, MichaelT, GlenH7, Joris Timmermans, Frank Shearar May 3 '13 at 21:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

5 Answers

I too very much liked algorithms in college ... well, I found that theoretical part of it to most employers has as much value as ... snow.

I will tell you, #2 and #3 are pretty much useless in the real world (in my 6 years as employee in 3 places), unless you are doing industrial research, which is a rare type of position. I would say concentrate on compilers - they are a bit tricky algorithmically, plus they make you a much better and more employable programmer. http://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html

Implementation of databases is also quite tricky, but that would be specializing, while knowledge of compilers is a more universal tool.

If you also like math, then machine learning knowledge is very applicable and well-rewarded these days.


To my critics: So ... you two alternative implementations, and you have proved that the complexity of both is O(m*log(n) + nk^2). Ok, two things come to my mind: A) Did you really need to get a master's degree in complexity theory to come up with that, or would a single undergraduate intro class to algorithms suffice (you can use Wikipedia and Google at work and read a bit). B) Great, you proved that the complexity the same, but what are the constants? How do two algorithms measure up, particularly if constants do differ and it is now the case of comparing apples to oranges? C) Do you use caching? Make many calls to the database? These things are very important, and I still wager that #2 and #3 are useless 95% of the time. And when they are not, deducing, and maybe even proving the formula should take at most a couple of days. Relative to that work, a lot more effort is needed to measure things empirically (yes, it is a black box, and hence performance testing is an art). Given that we have derived formulas first, we will know what are likely the important parameters, and then change those while keeping everything else fixed. If there is time and resources left, we could get more data to fill a volume. Of course, one would have to repeat the trials a bunch of times, to compute some basic statistics, and perhaps to try things out under unusual loads. That is hard work, but in my mind it has a lot more value than just the formula itself. Often the programmer just has to make an intelligent choice between a list, and array, a tree or a dictionary. On the rare occasion when a thorough performance analysis is required, still very little theory is required. The most important piece is profiling.

Therefore, I believe it would be wasteful to do a Master's degree / PhD in theory of computation / complexity and planning to work as a software developer. It surely helps to flex the brain muscles, and there is something to be said about pursuing one's love, but if one wants to be a developer, and one likes math (even if discrete), there are still better ways of getting education, having fun and being prepared for the industry.

share|improve this answer
+1 for machine learning <brofist> –  MattyD Jun 6 '11 at 1:21
actually #1 is often useless too. I don't know any person who has to write sorting algorithm by his own. usually we need if's and for's and a lot of technologies. –  Sergey Jun 6 '11 at 8:36
I highly disagree that #2 is useless. In many cases you'll be told to use/implement a specific formula/algorithm where an alternative would be more appropriate. In such cases you need some way to prove the answer is the same. –  edA-qa mort-ora-y Jun 6 '11 at 11:04
I also disagree that #3 is useless. I can't actually think of any job I've had where the complexity of some algorithm has not been important. –  edA-qa mort-ora-y Jun 6 '11 at 11:05
add comment

Of course #1 is the most important factor. However, don't completely ignore #3 as most here seem to suggest.

You should understand the Big O notation and know it for the algorithms you study. A merge sort is O(n lg(n)) while an insertion sort is O(n²). Can you explain why this matters? Are there cases where you should not use a quicksort?

Calculating the O notation yourself shouldn't be much trouble for the simpler algorithms like sorting or tree traversal. For the more difficult ones it can suffice to just know their efficiency.

Documentation will also often show the Big O for the implementation. Msdn does this for example. At the very least you should be able to understand what this means:

On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.

share|improve this answer
I agree that basics of #3 are needed, but I think that an intro to undergraduate algorithms tends to cover enough of #2 and #3. I would not suggest specializing in #2 and #3 to someone who wants to be a developer. There are many publications that put a lot of weight on #2 and #3; in fact it ain't considered a science if it is easy to read :) But this works is not done by the folks who aspire to become good programmers. I am not saying that math and coding is a bad combination; I am saying that little of #2 and #3 do intersect with daily task of a vast majority of programmers. –  Job Jun 6 '11 at 18:51
add comment

#1 is bread and butter for the vast majority of us.

You would definitely need #3 if you are in the business of improving software quality (better run-times, memory efficiency etc), working in high performance computing etc.

For 95%+ industry positions #2 isn't a must need.

Please refer to the books of Skiena and Levitin for an excellent discussion on these topics. Its been a while I have been studying these texts but every read reveals something new.

share|improve this answer
add comment

Job's answer is certainly correct for 95% of the job postings out there.

However, if you want to get a crack at a top-level computing science company (Google, for instance), you will not get past the phone interview stage without a deep and quick knowledge of any and all basic algorithms.

  1. In addition to standard sorting algorithms, ensure that you understand trees: B-trees, red-black trees, R-trees, and R*-trees.

  2. Learning to prove the correctness of an algorithm gives you more than that: it gives you insights into the algorithm, and can help you investigate new areas more quickly. Again, not something that a run-of-the-mill software house would be doing, but something you might come across in a high-end startup (or a Google).

  3. One of the things that Google and Facebook look at is download times of their Javascript and PHP. Why? Because if they shave 1% performance out of their existing systems, that means they can use 10 fewer servers per thousand servers... Get a better percent performance, and they save even more.

share|improve this answer
On #3 ... I wager that people who do not find proving this formula O(k^1.25+n*loglog(m)+ n^0.5*log(k)) amusing can still do a very good job at improving performance by a few percent. They will not prove it; they will measure it. Good point about Google and passing the interview though. –  Job Jun 6 '11 at 2:24
@Job: I mostly agree. Except that I contend that if you're just measuring, you're only doing blackbox improvements. Being able to prove it will get you whitebox improvements also. OK, I'm over-emphasizing for effect, but I hope my point is clear. –  Peter K. Jun 6 '11 at 2:32
add comment

I'm going to go along with Job here and say that for the Chambers Constant (that's 99.44%) of the time #2 and #3 are going to be useless for you in the real world of programming. Also I think you may want to branch out of just algorithms, so I'm not even going to recommend #1 particularly strongly.

What really makes or breaks real-world software is not algorithms (although they obviously help). What makes or breaks real-world software is proper use (and even design) of data structures. Great algorithms can be crippled by poor selection and/or design of data structures representing your data. Mediocre algorithms can be boosted quite easily by inspired choice of data structure representation.

share|improve this answer
my obviously more correct opinion, but knowledge of data structure and algorithm must go hand in hand, in the university I was attending, we were taught about using binary search over a linked list, and I said, wtf. –  Lie Ryan Jun 6 '11 at 8:54
add comment

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