Algorithms and data structures that are not mainstream?

Question

There are a subset of algorithms and data structures that are very common, well-studied and very helpful. Examples of these are Topological sort, quicksort, depth-first search; on the other hand, dictionaries, trees, linked-lists and to a lesser extent red-black trees, and tries, are examples of the latter.

However, there are other algorithms and DS that are not mainstream (not easily found in books) that we have learned on our own, have become a useful tool, and we are proud of using because they were hidden... maybe we found it in a dark paper from the dawn of computation in the 60s and it is still useful today, or we just made them up (why not?). My pet one is binary decision diagrams (BDDs). What is yours?

EDIT: A pity this was closed, but in all fairness, it was a duplicate, even if new answers were provided. In a scholarly fashion, I will summarize and thank everybody for answering. However, to appease my sense of "duplicate failure", I should also pay my respect to the original poster of the question (f3lix) and to the StackOverflow community by summarizing both posts, so a complete document remains. Thus (!), here is the list of algorithms and data structures that are not that common, duplicates removed:

• Bloom filters
• Maintaining order in a list
• Elevator algorithm
• Cuckoo hashing
• Skip lists
• Modifiable priority queues (can someone provide a link for this, please?)
• Non-Deterministic Finite State Machines
• Interval skip lists
• Dancing links
• Tries (or here, with a interesting use of it at this site)
• Suffix tries and Suffix arrays
• Splay trees
• Heap-ordered search trees (can someone provide a link for this, please?)
• Spatial indices, particularly R-Trees and KD-Trees
• Bit arrays
• Ropes
• Van Emde-Boas trees
• MX-CIF Quadtrees
• HAMTs
• Inverted indices
• Disjoint sets
• Pairing heaps
• Treaps
• Binary space partitioning trees
• Binary decision diagrams
• Fusion trees
• B+ trees
• Quad trees
• Octrees
• Range trees (how much we love trees...)
• Linear hashing and Spiral hashing
• Huffman trees
• Circular buffers
• Finger Trees
• Simplex algorithm
• Zobrist Hashing

I hope this will be useful as a reference at some point.

Answer 1

I like to write lexers/parsers by hand.

The challenge is to be as robust as possible, and to provide the most optimal error strategy (both recovery and messages).

Answer 2

Not necessarily my pet algorithm, but definitely one of the most memorable is "maintaining order in a list" :) not only because it sounds first rather trivial... isn't list about maintaining an order? I used this once in a real-life project, and it took a while to find it. And it was very useful! Here one variant solution (PS paper).

Answer 3

I've had to implement modifiable priority queues (where items can be removed, or their priorities changed) twice.

Answer 4

I really like Bloom Filters for checking if an item has been seen before, when dealing with millions of items.

Dictionaries or Maps or Hashtables are usually used for this purpose, but Bloom Filters give you significantly better memory usage for a tiny (controllable) accuracy trade-off.

Answer 5

An operating systems course I took in college opened my eyes to quite a few algorithms I wouldn't have thought about otherwise. I particularly liked the Elevator algorithm. The instructor for the course presented the real-world elevator scheduling problem to us, made us come up with our own solutions, then showed us how it related to disk scheduling. It was quite the "Aha!" moment.

Answer 6

Since the Bloom filter answer made me think of probabilistic structures: Skip List.

Answer 7

Cuckoo Hashing

Answer 8

And they're not exactly obscure, but they are underused IMO: NFA.

Answer 9

Interval Skip List if only for the term "stabbing query". :)