Live data from Hacker News

The Most Important Algorithms

risc.jku.at

21–30 of 50 posts

Re: The Most Important Algorithms

#21
post #4

quite a lot of structure amongst these algorithms that the list misses out: - dynamic programming comes from solving Bellman's equation and Q-learning is an approximate means of doing dynamic programming. - It's possible to do beam a* search, where beam search, a* search, and best-first (greedy) search are special cases. - in the continuous domain, greedy search is essentially gradient ascent. - you can use discrete…

1) Just do EM with parameters in an arbitrary semiring and you generalize nicely to all the special cases you mentioned (and more)

2) I see how all of EM is coordinate ascent, but I don't see how the M step is gradient ascent. Where the gradients at?

3) Second-order optimization methods can be pretty tricky and fall apart for large problems. Stochastic gradient descent ftw.

Re: The Most Important Algorithms

#22

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 re…

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.

Any good physics book that I could look into? Preferably books that integrate physics with programming?

Re: The Most Important Algorithms

#23
post #19
post #15

Erm... How did this list include the merge sort and heap sort, but not the quicksort?

I don't agree with that list, but I think quicksort is given way more weight than it deserves. I guess it's a desired result of whomever named it "quicksort". It's not particularly quick, has horrible worst case guarantees (which, if you care to improve, would make it slower still and very complicated), and is easy to get wrong on many accounts (repeating elements; already sorted input; unlimited recursion depth). he…

I agree, but you have to jump all over your data when you do a heapsort, blowing your cache.

It has nice worst-case guarantees, but a well-implemented quicksort has good cache locality.

Re: The Most Important Algorithms

#24

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 re…

It's a good list, but there's been a few articles on here that talked about hashing and other security-related algorithms. Generally speaking, if you're implementing one, you're doing it wrong. Of course knowing about them and how they work is essential.

Re: The Most Important Algorithms

#25

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 re…

It's a good list, but there's been a few articles on here that talked about hashing and other security-related algorithms. Generally speaking, if you're implementing one, you're doing it wrong. Of course knowing about them and how they work is essential.

Not all hash functions are cryptographic hash functions.

Re: The Most Important Algorithms

#26

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 re…

It's a good list, but there's been a few articles on here that talked about hashing and other security-related algorithms. Generally speaking, if you're implementing one, you're doing it wrong. Of course knowing about them and how they work is essential.

The same goes for a bunch of things on my list, eg. sorting, compression, and SVMs. I don't think I've ever had to implement a sort algorithm outside of coursework or an interview context.

I included them because understanding how they work can still be pretty critical to using them effectively. I'll never have to implement a sorting algorithm. I do, however, have to understand that a best-case comparison sort is O(log N), and that if I just want to scan out the top-10 items in a long list, I'm better off with a linear scan (O(N)). I need to know that keeping data in sorted order will let me binary-search on it, for O(log N) access, and that cache & memory hierarchy effects often mean that this is faster than the O(k) access I might get with a prefix trie. I need to know that passing nearly-sorted data to QuickSort, in the absence of something like median-of-3 partitioning, can result in pretty pathological runtimes. I need to know that QuickSort can be done in-place, but MergeSort requires O(N) additional space. OTOH, MergeSort can be done efficiently in situations where mutation and random access are not allowed (eg. tape drives, functional languages), which other sorts don't do so well. I need to know what a stable sort is (very important for UI programmers!) and which algorithms have that property. I need to know that passing the first 80% of sorted input to a statistical or machine-learning algorithm and then saving the last 20% for your test set will give you pretty odd results. :-)

Hashing is similar: you don't want to implement it yourself. You do want to understand the various approaches and their limitations.

Re: The Most Important Algorithms

#27
post #22

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 re…

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 eas…

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

Re: The Most Important Algorithms

#28

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 re…

Nicely observed, but I have two just for the records (again, I know):

i.) this is a list of/for CS professors; RISC expands to Research Institute for Symbolic Computation which is a CS/Math department of Prof. Buchberger who discovered the famous Groebner bases.

ii.) AFAIR (too many years gone since), the A* algorithm is pretty much a generalization for graph traversal. I remember my professor showing us that how by either prepending or appending nodes to visit to a list either gives depth-first or breadth-first traversal. So I think in a way at least both lists agree on the most important algorithm...

edit: obviously I forgot to state that a tree is a graph, too.

Re: The Most Important Algorithms

#29
Good list.

I would include some more pragmatic algorithms, such as Frank Liang's hyphenation algorithm (PhD thesis at Stanford in 1983) http://www.tug.org/docs/liang/

Also De Casteljau's algorithm for Bezier curves from 1959 and deBoor's algorithm for B-splines.

The above are the ones that I have had to implement in the past as part of my work. There is a whole bunch of other algorithms in computer graphics that are equally (or more) important, which many of us rely on but fortunately don't have to implement.

Oh, another classic, pragmatic algorithm is John Carmack's implementation of BSP-based pseudo-3D rendering for the Doom game engine in 1993. See http://doom.wikia.com/wiki/Doom_rendering_engine

Re: The Most Important Algorithms

#30
post #5
post #3

Earlier quoted context omitted.

Instead of going by a checklist, try to approach it by domain: Searching; Sorting; floating point, integer computing, and bit-manipulation; numerical analysis and computation; DSP; optimization and dynamic-programming; information theoretic stuff like compression and encryption; graph theoretic algorithms; symbolic algebra; geometric and hierarchic data structures and algorithms; statistical, probabilistic and infere…

I am going through Cormen et al. with the objective of getting my feet wet but the whole process is painfully slow. I thought it would be nice to have at least some familiarity on the widely used algorithms across the globe. However, you are right on ditching programming languages with huge boot times. I am happily trying out my algorithms in Python.

CLR is an extremely well written algorithms textbook, but I use it more as a reference than for self-study. My first algorithms book was Sedgewick's Algorithms (where all algorithms were presented in Pascal), which is a very good algorithms text that is much lighter on several aspects.

Recently, however, I came across the following gem: Algorihtms + Data Structures = Programs, by Niklaus Wirth. (an Oberon version of 1994 is available for free: http://www.oberon.ethz.ch/WirthPubl/AD.pdf). I think this is hands down one of the best algorithm books. It amazes me how much content Niklaus Wirth is able to present in concise, yet crystal clear writing. Besides the usual algorithms, he includes very interesting applications that probably no other book does: using the partitioning of QuickSort to find the median (pg. 56 in above PDF, Section 2.3.4), based on algorithm by C.A.R. Hoare, and an in-depth discussion of polyphase sort (pg. 70, Section 2.4.4), which might be interesting for heavily distributed sorting (that at least what I imagined as a possible application when I recently re-read parts of it).

Post reply on HN