Aside from artificial intelligence, which algorithms commonly taught in university data structures and algorithms courses were actually invented relatively recently? Many familiar techniques seem to date back decades or even centuries, so I'm curious which important or widely used algorithms are newer than people might expect.
5 Answers
Density-based clustering also gives a useful timeline. DBSCAN was introduced in 1996 and handles irregularly shaped clusters better than older methods such as k-means. HDBSCAN, developed much later, extends the idea to deal more effectively with clusters of varying density. More generally, online algorithms, streaming algorithms, graphics techniques, and bioinformatics contain many newer developments because they address data and hardware problems that became widespread only recently.
Cryptography is one of the clearest areas where important algorithms are relatively recent. RSA dates to 1977, elliptic-curve cryptography became prominent later, and SHA-3 was standardized in 2015 using a sponge construction that differs substantially from SHA-2. SipHash, created in 2012, is another newer hashing algorithm designed to reduce certain hash-table denial-of-service risks. Cryptography keeps producing new algorithms because attackers actively look for weaknesses in existing ones.
Timsort is a good example. It was developed around 2002 and combines ideas from merge sort and insertion sort while taking advantage of ordered runs that already exist in real-world data. Introsort, another practical sorting algorithm commonly used in standard libraries, dates from the late 1990s. It starts like quicksort but switches strategies when recursion gets too deep.
The name of the C library function can be misleading too—some implementations of qsort use merge sort or another variant rather than literal quicksort.
Distributed-systems algorithms are often much newer than the classic textbook material. Raft, a consensus algorithm designed to be easier to understand than Paxos, was published in 2014 and is used in many clustered systems. MapReduce was described by Google in 2004, although many of its underlying ideas had appeared earlier in parallel and functional programming.
The exact implementation varies by system, though, so it’s safer to say Raft is common in distributed databases and coordination services rather than assume every database uses it.
Lock-free data structures became especially important in the 1990s and 2000s as multicore processors became common and memory access increasingly lagged behind CPU speed. Many lock-free linked lists, queues, and related techniques were developed or refined during that period. They aren’t always part of an introductory course, but they’re a good example of algorithms driven by newer hardware realities.
Even algorithms from the 1970s can feel recent compared with foundational mathematics, but in practical software terms they’ve been around for quite a while.