4 ms·
This reads like a textbook, i.e. it's algorithms that are highly useful to CS professors and students but not necessarily to practitioners. If I had to pick a
by nostrademons 16y ago
This reads like a textbook, i.e. it's algorithms that are highly useful to CS professors and students but not necessarily to practitioners. If I had to pick a top-10 list based on my professional experience, it would be:
1. Tree traversal. This comes up all the time, from directory walks to DOM traversal to code analysis to folds over abstract data types. It's also something that you need to know and can't always rely on having a library function for, because many things exhibit tree-like structure without actually being instances of your language's Tree data type.
2. Hashing. Obviously as a base for hashtables (which are often your dictionary data structure of choice), but also as a general technique for generating a small fingerprint from a large set of data.
3. Statistics - mean/median/mode, but also things like confidence intervals, regressions, sample sizes, how to make sure your populations unbiased, etc.. You are evaluating your product, right? Knowing how to make good inferences from data is critical, particularly since there're lots of ways you can do it wrong.
4. Sorting. This can usually be hidden behind a library function, but it's useful to understand because many other algorithms have very different (and often better) performance characteristics if the input data is kept sorted. Binary search falls into this bullet point too.
5. Data compression algorithms. Another one that you'll rarely have to directly implement, but knowing their characteristics helps you make good speed/space tradeoffs for the rest of the system.
6. Bloom filters. This is one that I never learned in school but tends to be incredibly useful when dealing with massive data sets. Oftentimes, you want to be able to quickly reject elements if they're not in a set, but don't really care about it taking a while if they are in a set (because you expect that many more elements will be outside of the set than inside it). A Bloom filter is one of the fastest, most space-efficient ways to do this.
7. Topological sort. Dependency graphs come up all the time in practical programming problems, and usually you want a way to linearize them into a list of tasks that you can perform in order. It's also a shame that many languages' standard libraries don't have a topological sort function, so oftentimes you will have to implement this one yourself.
8. Support vector machines. These are your bread & butter machine-learning classifiers, and are really nice to know when you've got a bunch of data and want to try to automate some rote classification job.
9. Physics simulations. I've found it surprising how useful my intro physics course knowledge has been. Things like vectors, position vs. velocity vs. acceleration, damped harmonic oscillators, FFTs, etc. It's most useful when building UIs and games - oftentimes, you can make a UI feel significantly more natural by adding easing functions that behave like acceleration when you ease in and frictional damping when you ease out.
10. Unification. I'm probably biased because a lot of my hobby programming is in compilers & type systems, but unification comes up all the time in compilers, and is a really general technique for equation solving.
- j_baker 16y agoNice list. I would probably generalize #1 into graph traversal though.
- nostrademons 16y agoProbably yes. I figure that trees come up so often that tree traversal on its own would be #1. I did add topological sort to the list after remembering just how many times (and for different domains!) I've had to implement one, but other graph traversal algorithms like BFS/DFS are quite useful too.
- kiba 16y agoPhysics simulations. I've found it surprising how useful my intro physics course knowledge has been. Things like vectors, position vs. velocity vs. acceleration, damped harmonic oscillators, FFTs, etc. It's most useful when building UIs and games - oftentimes, you can make a UI feel significantly more natural by adding easing functions that behave like acceleration when you ease in and frictional damping when you ease out. Any good physics book that I could look into? Preferably books that integrate physics with programming?
- nostrademons 16y agoI believe my course used Halliday, Resnick, and Walker, but at the intro level, basically anything should do. I wasn't even really thinking about the integration with programming - the parts I've used have mostly been just knowing what the basic equations were, along with representations like vectors and such. If you have a function of t, then all you need to do to simulate it is advance t by some infinitesimal amount (based on the frame rate, usually) and then compute your new positions. I guess that when you get to more complex simulations, then things like fast matrix multiplication and symbolic differentiation may be useful, but I've never actually used them in my own programming.
- signa11 16y ago> Any good physics book that I could look into? Preferably books that integrate physics with programming? any game physics book would do that for you e.g. http://www.amazon.com/Game-Physics-Interactive-3d-Technology/dp/1558607404 http://www.amazon.com/Game-Physics-Interactive-3d-Technology... also there is structure-and-interpretation-of-classical-mechanics (yes, by the same cohort)