3 ms·
Ask HN: Favourite Lesser-Known Alg?
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
- jdmg94 4y agonice try recruiters
- da-bacon 4y agoThe k dimensional Weisfieler-Leman algorithm https://www.iti.zcu.cz/wl2018/wlpaper.html https://www.iti.zcu.cz/wl2018/wlpaper.html Connect a huge number of graph isomorphism algorithms with a algebra.
- dongecko 4y agoThe 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 4y agoHadlock’s Algorithm for optimal pathing/maze routing. Definitely changed the way I think about using BFS/DFS to find paths.
- cpach 4y agoClickable link: https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93...
- rkwz 4y agoBig fan of all the fuzzy matching algorithms: * Levenshtein * Jaccard * Cosine * Jaro–Winkler * Soundex and many many more!
- vintermann 4y agoThe 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 4y agoSome 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