> “This thing might as well have been discovered 50 years ago, but it wasn’t,” Thorup said. “That makes it that much more impressive.”
this is so cool to me, it feel like a solution you could* have stumbled upon while doing game development or something
*probably wouldn't but still
Rather than the academia.
Just a hunch tho
Years ago, however, I came across a paper for optimal convex polygon decomposition that had zero implementations and the paper was so complicated.. couldn't figure out how to implement it myself. I came up with something new and published it which was apparently enticing enough to be picked up by at least one game library. So that was neat.
Merge sort is supposedly invented in 1950, it’s more likely it was invented in 1050 than 1950. Sort a room full of documents for me. You have three minions, go.
But a room of five clerks all taking tasks off a pile and then sorting their own piles is merge sort at the end of the day. Literally, and figuratively.
given Al Kwarizimi lived ~12 century (if memory serves right) it is a fairly old term in this regard.
when was it that modern people started using the word, I'd bet beginning of 20th century, but this is a wild guess.
when did everyone started calling algorithms "ai", well perhaps ~1960 ?
Myself and others from the math schools knew this algorithm in 8th grade for sure, as we been already using it in 9th grade for competitions. This does not mean all my classmates knew it, of course not.
So it depends who you teach this to. Theoretically - you should be able to, practically - well, perhaps not so much, as math is not the only thing 8th grader learns, in fact his head is bombarded with ... dozen disciplines at a time.
Besides, I recently met a classmate, previous IoI medalist, who works quant-something somewhere for 15th + years, and is a PHD and everything. We start talking about mathematics and I find to my total surprise he knows very little about grammars, never used them. He remembers Dijkstra or Ford-Fulkerson, but only as a title, while I'm sure he learned these at some point in Stanford, as the shortest-path and A* was not something we had in textbooks back in the 90s for sure.
Many textbooks make it sound harder than that because they want to examine complex data structures that make various parts of that as fast as possible. But the complexity is the implementation of the data structures, not Dijkstra's algorithm.
I was able to read halfway through the book before it started getting too complex for my teen mind.
so, can it be taught? - yes is it trivial - I would not dare say, but is elegant in simplicity do people understand and remember it easily - no, they don't
should you decide to prove me right, well - try to teach it to someone, but also require that he not only understands but implements it. well those who could do this in 8th grade were those going to Olympiads in Informatics.
perhaps things have changed since the 90s and children are smarter today. so my bet is you can teach it to 5th graders, not sure to what effect though.
We give a deterministic O(mlog2/3n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m+nlogn) time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.
Also the curently best factorization algorithm (GNFS) is at exp(k*log(n)^1/3log(log(n))^2/3).
Intro algorithms classes just tend to stay away from the really cursed runtimes since the normal ones are enough to traumatize the undergrads.
But if you're not implementing AI or game engines, some of the linear algebra space may be a road less traveled.
Im most curiosity how the algorithm fulfil the "global minima" that djixtra guarantees. The clumping of front-tier nodes seem prone to missing some solutions if unlucky.
Additionally, the `n` in the complexity only matters if for the Dijkstra approach you actually need a frontier of size proportional to `n` [remember that for open-grid-like graphs, the frontier is limited is limited to `sqrt(n)` for a plane, and for linear-ish graphs, the frontier is even more limited].
Also note that the "sorting barrier" only applies to comparison-based sorts, not e.g. various kinds of bucket sorts (which are easy to use when your weights are small integers). Which seems to be part of what this algorithm does, though I haven't understood it fully.
ljlolel•6mo ago
larodi•6mo ago
kzrdude•6mo ago
larodi•6mo ago
bob1029•6mo ago
https://en.wikipedia.org/wiki/Splay_tree
teraflop•6mo ago
His Turing award writeup gives a pretty broad overview of his research contributions: https://amturing.acm.org/award_winners/tarjan_1092048.cfm