7 Algorithms That Rule the World(youtube.com)
youtube.com
7 Algorithms That Rule the World
https://www.youtube.com/watch?v=DsXtYx7RfqE
13 comments
Something I've wondered for a while: how many things actually use Dijkstra's algorithm, in practice? I know how it works, and I've implemented shortest-path graph algorithms a few times, but it's always been fairly easy to find at least some kind of admissable heuristic, so why would you implement Dijkstra over A-star? (edit: stupid hacker news markup wont let me escape the asterisk)
Obviously, when your graph has some sort of geometric interpretation (i.e. a map or something), euclidian distance is the obvious choice (or Manhattan distance if you're on a grid, etc.), but even for relatively abstract things you might use graph search for you can usually figure out something. Like, if you're trying to find the shortest solution to a sliding block puzzle using a graph algorithm (where each node connects to all other nodes you can get to in one move), you can use some sort heuristic based on the number of inversions, or whatever. Even if your heuristic is kinda bad, it's almost certainly better than no heuristic at all.
Dijkstra's algorithm has always seemed to me to be the "canonical academic shortest-path algorithm that always works", but in reality everyone uses A-star instead, because for all practical purposes it's way better, and not much more complicated to implement.
Obviously, when your graph has some sort of geometric interpretation (i.e. a map or something), euclidian distance is the obvious choice (or Manhattan distance if you're on a grid, etc.), but even for relatively abstract things you might use graph search for you can usually figure out something. Like, if you're trying to find the shortest solution to a sliding block puzzle using a graph algorithm (where each node connects to all other nodes you can get to in one move), you can use some sort heuristic based on the number of inversions, or whatever. Even if your heuristic is kinda bad, it's almost certainly better than no heuristic at all.
Dijkstra's algorithm has always seemed to me to be the "canonical academic shortest-path algorithm that always works", but in reality everyone uses A-star instead, because for all practical purposes it's way better, and not much more complicated to implement.
OSPF routing protocol(IGP) on network gear use Dijkstra. Most network within mid/large enterprise use it.
On a unrelated note it's fascinating to me that the some obscure algorithm came way before actual technology implementation. reminded me of https://xkcd.com/435/
math -> algorithm -> tech
And hopefully not RSA much longer; like RC4, it's completely insecure if you use it in the simple, obvious way you might get from a textbook. ECC is superior in almost every way. Now Diffie-Hellman --- that there is a venerable algorithm.
True. With exponentially growing computing power, many cryptographic algorithms will be at risk. Everything evolves with time. Commonly used compression algorithms like JPEG or MP3 are starting to being obsolete as well. So what I put in the list are algorithms that put crucial fundaments for computing world.
But anyway, it's a matter of opinion. 10 people could come up with 10 different lists.
But anyway, it's a matter of opinion. 10 people could come up with 10 different lists.
Of course. The individual algorithms may change, but algorithm families reflect problems nature herself has given us, and we'll always have to deal with these broad classes of problem.
Thanks for your feedback. I mentioned at the end of video that this list is not comprehensive and there are many more... maybe I should put it also into description.
Thank you. This title is clickbaity.
While FFT is pretty powerful and heavily used, I doubt you can't have Internet without it.
FFT is used in RF communication: WiFi, Cable Modem.
It's true we don't need it but it is the majority of access technology for the "last mile". FFT in Fiber optics are becoming more prevalent.
The whole networking is dependent on FFT.
I don't think it's required. Can be used for many things in networking, yes, but not required.
EDIT: 100 subscribers! Thank you guys! :)
1. Fast Fourier Transfrom
2. Link Analysis
3. Data Compression
4. Dijkstra's Algorithm
5. RSA Algorithm
6. Proportional Integral Derivativ Algorithm
7. Sorting Algorithms
I guess that makes sense. Skipping any AI or computer graphics algorithms or optimization or database (paxos) or scaling/parallel algorithms.