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