Algorithm Study [duplicate]

Question

This question already has an answer here:

• Is there a canonical reference on algorithm design? 8 answers

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.

Answer 1

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.

EDIT:

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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.