HN Explorer

Ask HN: Favourite Lesser-Known Alg?

22 points by skruger ↗ HN
I came across a reference to the Douglas-Peucker line simplification algorithm in the context of lossy compression for GPS tracks. It's a beautiful thing, but not widely known, perhaps? It made me think: what other gems are there that are not part of the standard CS 101 curriculum? Kalman filtering?

https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

8 comments

[ 2.7 ms ] story [ 22.1 ms ] thread
rkwz
Big fan of all the fuzzy matching algorithms:

* Levenshtein

* Jaccard

* Cosine

* Jaro–Winkler

* Soundex

and many many more!

vintermann
The Burrows-Wheeler transform. Especially the bijective variant. I feel like there's some profound magical thing hidden inside it that I sadly don't have nearly enough algebraic chops to find.
JoshCole
Some of my favorites are:

Best First Upper Confidence Bound Tree Search.

Monte Carlo Counterfactual Regret Minimization.

Temporally Weighted Averaging - eg discount the first ten samples.

Markov Chain Monte Carlo Sampling

Unification

dongecko
The Frank-Wolfe algorithm for optimization. Christian Bauckhage has a couple of papers, where he uses it to connect optimization problems to the fix states of a certain type of recurrent neutral networks (echo state networks).

The Marchenko-Pastur distribution derives from random matrix theory a nice theoretical border to estimate if a principal component is more noise then data.

Also I am a huge fan of all sorts of embedding/projection/matrix factorization algorithms and I use them quite regularly.

midlightdenight
Hadlock’s Algorithm for optimal pathing/maze routing.

Definitely changed the way I think about using BFS/DFS to find paths.