181–190 of 507 posts
Another favorite is RAFT, simply because of how elegant and simple it is and how easy it is to understand.
Also - I used to work in a company that did P2P video streaming (pre WebRTC) and the way the protocol leveraged Reed Solomon Coding was just awesome. https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...
Honorable mention: Kahan summation algorithm https://en.m.wikipedia.org/wiki/Kahan_summation_algorithm
It would be hard to beat Floyd–Warshall algorithm. Think about the problem of finding shortest paths between all pairs of nodes in graph. Sounds trivial? Would you believe if someone told you it can be done in literally 5 lines of code? When I saw that for the first time I was in the disbelief. The elegance comes from these fact, - Very non-trivial problem - Just 5 lines of code - Probably the most language agnostic…
> Probably the most language agnostic algorithm Are you sure about this point? I'd like to see a purely functional implementation of this, e.g. in Haskell without monoids. I believe it's significantly harder than a C implementation (which is indeed a few lines)
import Data.Array
fw :: Int -> Array (Int, Int) Int -> Array (Int, Int) Int
fw 0 graph0 = graph0
fw k graph0 =
let fw' = fw (k - 1) graph0 in array (bounds graph0)
[ ((i, j), min (fw' ! (i, j)) ((fw' ! (i, k)) + (fw' ! (k, j))))
| (i, j) Binary search. Very simple, incredibly powerful; can search on data or math function. It's the basis for other CS concepts. JS implementation: https://gist.github.com/netgusto/90c8e0e7019a832cbf95eac58e1...
I've used it as a very simple equation solver in a pinch. Yes, it's a very naive approach for most equations, but getting started solving it satisfactory with a solution given is very welcome.
Second favorite is the LISP REPL. Specifically the Eval function, thanks to this classic video of Sussman https://www.youtube.com/watch?v=0m6hoOelZH8
It would be hard to beat Floyd–Warshall algorithm. Think about the problem of finding shortest paths between all pairs of nodes in graph. Sounds trivial? Would you believe if someone told you it can be done in literally 5 lines of code? When I saw that for the first time I was in the disbelief. The elegance comes from these fact, - Very non-trivial problem - Just 5 lines of code - Probably the most language agnostic…
> Probably the most language agnostic algorithm Are you sure about this point? I'd like to see a purely functional implementation of this, e.g. in Haskell without monoids. I believe it's significantly harder than a C implementation (which is indeed a few lines)
It's such a simple formula, but manages to smooth and filter signals nicely.
I also have spent way too much time trying to get an implementation of it right, so there's a little stockholm syndrome.
Diffie–Hellman. I know that cryptography can get much fancier and more clever, but Diffie–Hellman took a concept my intuition told me was impossible and showed that it's possible in a really simple, elegant way. Learning about it was the first time I realized how beautiful the math behind computer science is. It's also a great insight into just how fundamental the concept of computational complexity is.