The Most Important Algorithms
risc.jku.at
risc.jku.at
- 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 differentiation to find the gradients for gradient ascent (actually, i would replace the first order method suggestion of this list with newton-raphson or some quasi-newton raphson method like BFGS).
- EM ties some bits together.
- if you replace the max of the viterbi algorithm with a summation, then you get the sum-product algorithm which is essential in the E step of EM. if you use viterbi instead of sum-product, you get something known as zero-temperature EM, which is an approximate form of EM
- the M step of EM is typically just gradient ascent!
- you can use max flow to do a similar thing to viterbi on certain graphs
and so on...
Can you elaborate on the general search procedure?
Is there a good resource that ties algorithms together like you've done here, but less concise?
the general search procedure is just A* search but with the beam search pruning each time you expand the fringe of exploration.
i don't know a good source, i picked this up from a bunch of courses/research.
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.
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.
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.
Any good physics book that I could look into? Preferably books that integrate physics with programming?
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.
any game physics book would do that for you e.g. http://www.amazon.com/Game-Physics-Interactive-3d-Technology... also there is structure-and-interpretation-of-classical-mechanics (yes, by the same cohort)
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.
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.
1. If it is a stack, then you have a depth-first search, which visits all children first and then moves on to siblings.
2. If it is a queue, then you have a breadth-first search, which visits all siblings first and then starts recursing into children.
3. If it is a priority queue keyed by edge weights, then you have Dijkstra's algorithm, which will find the shortest path to any node in the graph.
4. If it is a priority queue keyed by in-degree of nodes, then you have a topological sort.
5. If it is a priority queue keyed by the lowest edge weight such that the endpoint of the edge is in the black set, then you have Prim's algorithm for minimum spanning trees.
You can have more exotic data structures too, eg.:
6. If it is a linked-list encoding of a stack done through pointer reversal, you have a mark & sweep garbage collector.
7. If it is a test on whether the pointer points to from-space or to-space, you have a Cheney-style breadth-first copying garbage collector.
I'd never seen a formalism that described this - it was just something I figured out when I was implementing my 3rd or so topological sort. I assumed that something like that must exist though - the notion of white/grey/black sets for graph traversal is well established in at least the garbage collection literature, and from there it's a short leap to figure out what structure of the grey set corresponds to which graph algorithm.
I just took a quick look at the A* entry in Wikipedia - I've heard of it but never had a reason to implement it myself - but it seems like it's a generalization of Dijkstra's algorithm where edge weights can be arbitrary functions. In this case, it's the same as case #3, but the keys to the priority queue are a function of the node instead of a straight list of edge weights.
In A* if you use a heuristic to select an edge (using a priority queue, i.e., your #3) it gives a best-first search. But it is is possible to just use a stack/queue an forget about the heuristic, then you get a nice generic way of tree (graph) traversal.
Regarding your use of white/black/grey lists: in a tree (which is acylic), you would only need a list of nodes to visit, however, in a general graph you need to keep a list of nodes that you have already seen/visited so as not to get into a cycle when the graph is cyclic. In tracing garbage collection algorithms this is often used because the live program data generated by the mutator is cyclic, or at least potentially can be. Thanks for mentioning this, though I know my way around gc stuff, too, I would have never come up with this link here! Probably it is a good advice to anybody interested to spend some time reading into garbage collection algorithms, they contain many interesting algorithms on graphs, such as the Deutsch-Schorr-Waite algorithm for tree traversing without requiring an additional stack. The definitive book on garbage collection is 1996's Jones and Lins: http://www.amazon.com/Garbage-Collection-Algorithms-Automati...
http://blog.sigfpe.com/2009/07/monad-for-combinatorial-searc... http://spivey.oriel.ox.ac.uk/mike/search-jfp.pdf http://www.cs.au.dk/~gerth/papers/jfp96.pdf
If you really don't like yourself, try digging here:
http://hackage.haskell.org/packages/archive/pointless-haskel... http://comonad.com/reader/2009/recursion-schemes/
Let's say you’re building a system to quickly find the degree of separation between two people on a network. For simplicity assume each node connects to 4 random other nodes. If you start from one end and do a breadth first search you would need to try ~(4^N) nodes to find the link. However, if you start from both ends and do a breadth first search you can try ~2 * (4^(N/2)) nodes to find that same connection.
Diffie-Hellman key exchange as well as it is so simple and so wonderfully counter-intuitive.
+---A---+
|...........|
B h:1....E h:4
|
C h:2
|
D h:3
The traversal order according to Best First Search would be:
{A, B, C, D, E}
While A* will search by g(x) = h(x) plus d(x), the latter being the distance function from the start note to the given node. So, assuming the distance function to be equal to the depth of the node in the tree it would traverse it this way:
{A, B, C, E, D}
g(D) = h(D) + d(D) = 3 + 3 while g(E) = h(E) + d(E) = 4 + 1 = 5, so E goes first.
The whole point of big encyclopedic texts like Cormen et al. is to wet your feet and give you a broad exposure to various techniques. That way you have a small idea on what you want to use next, and you know which domain to focus your research.
My one recommendation is to ditch programming languages with huge boot-times when playing with algorithms. You want something that you can interact with live and see results; in that regard, even a symbolic algebra system like Maxima would be better than C, C++ and Java. Lisp and Python would be ideal for most algorithms.
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).
It gives you questions that you write programs to solve, then judges your programs against test cases. It's fantastic. The questions are difficult, but never impossible, and they drill you well on diverse algorithms, building on previously learned concepts, so that you really understand the material.
nice list I'd also nominate :
support vector machines, back prop neural net training, delaunay triangulation, floyd-warshall, kruskal's mst, newton's method, edit distance algorithm, huffman coding or something with compression (I'd vote zip), some kind of reduction algorithm and we can't forget simulated annealing
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
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).
heapsort is simpler than quicksort, and has the best worst-case complexity you can get. It's not stable, but then neither are most quicksorts.
quicksort has its place, but it gets a lot more attention than it deserves.
It has nice worst-case guarantees, but a well-implemented quicksort has good cache locality.
I don't think that's true if you average over the available distribution of _implementations_ in the wide. Almost all implementations do one to three of the "crimes" I mentioned above. And frankly, I've met too much real world cases that triggered an n^2 behaviour on an existing implementation to ever settle for anything with worse than n*log n worst case.
If you're looking for the fastest-in-both-theory-and-practice algorithm, that's TimSort, but it's not in place. The places _in practice_ where Quicksort is the right answer are few and far between. I haven't seen any in the last 10 years.