What are examples of recent relatively simple 'toolbox algorithms'?

Question

Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc. There are also several relatively standard data structures, such as hash maps or prefix-trees, etc. which are not super complicated but not trivial either.

Question: what are some examples of recent (say later than 1990) data structures and/or algorithms which are general enough and useful enough to be included in a modern Introduction to algorithms course?

There are some examples of algorithmic breakthroughs which almost fit here that I know of (I am mainly a mathematician). First one is the algorithm that in polynomial time determines if a number is prime or not. The second one is the graph isomorphism problem, which is shown to be not NP-complete by exhibiting a faster algorithm. Both of these, I kind of disqualify since they are too advanced from a math point of view. I am more looking for examples which naturally fits among the ones listed above (which are hard to come up with yourself, but easy to understand when they're explained).

Or, did our academical ancestors in the 1950s already discover all the 'classics'?

Answer 1

More attention has been given recently to sketching and streaming data structures, such as Bloom Filters, Count Min Sketch, HyperLogLog.

Related, and also gaining popularity, are linear-algebra-based data-summarization type algorithms: compressed sensing; the Johnson-Lindenstrauss transform; principal component analysis via the singular value decomposition.

Answer 2

Suffix arrays, with linear time construction. There are various algorithms, they're relatively approachable, and applications are plenty. SA-IS dates to 2009.

Soft heaps, they're not that complex, and have some neat applications. Dates to 2000, some newer tricks are more recent.

For off-line lowest-common-ancestor, Tarjans union-find based algorithm gets all the attention. It's not bad, but Schieber&Vishkins bit-manipulation based algorithm is also neat. Dates to 1988, which is before 1990, but apparently that's recent enough that it remains largely unknown.

Asymmetric numeral systems have largely replaced Huffman as the "default entropy coding algorithm" in the past decade or so. IDK if that deserves to be in introduction to algorithms, but Huffman coding sometimes shows up too

Answer 3

Quantum algorithms would fit this, if one has time to introduce the model -- specifically, Grover search and possibly Shor's algorithm.

Answer 4

You could look at the multiplicative weights update method. Specific instances of this technique have been known since the 1950s, but it's only been recognized as a very useful general algorithmic technique in the last decade or two.

Answer 5

I think we could include submodular optimization. Many common optimization problems can be framed as maximizing or minimizing submodular functions subject to natural constraints. Examples include max cut and min vertex cover. Research in the area dates to the late 1970s, but submodular optimization and applications have received much more study and attention since 2000.

Answer 6

Perhaps Markov Chain Monte Carlo. Like most other answers, it can be traced farther back, but rose to much more prominence since the mid-90s. In general, Markov chains and (random) walks on graphs are good topics for early algorithms classes, as they're useful later both in applications and theory.

Answer 7

I guess it depends on what constitutes "too advanced from a math point of view." It is natural that modern algorithmic ideas will involve more modern mathematics.

The theory of Linear Programs (LPs) was a huge breakthrough (from the 40's) and many modern algorithms and algorithmic ideas are based on the theory of LPs or solving an LP. One modern example is Primal-Dual methods. These are algorithms that use the theory of LP duality to find a solution but don't actually need to solve any linear programs (LPs). Actually, Kruskal's minimum spanning tree algorithm, Dijkstra's shortest path algorithm, and some other classical network algorithms can be viewed as primal-dual algorithms.

However, understanding the theory of LPs would probably take too much time to be included in an intro to algorithms course. It also requires knowing a little linear algebra, so it might not be what you are looking for.

An idea that might fit better is that of randomized algorithms. Karger's contraction algorithm for finding minimum cuts is a good introduction that can be understood and analyzed with very little math.

Answer 8

Montgomery's ladder and a whole host of other algorithms developed to mitigate side-channel attacks only appeared in the 1980-1990s. They're conceptually quite simple to understand, and the rationale behind them could be explained in a couple of sentences to a layperson. https://www.jstor.org/stable/2007888

Answer 9

Some search based algorithms such for finding(or enumerating) Maximal Cliques have been around for a while, eg Bron-Kerbosch from the 70s. Related to such maximal clique finding algorithms could be that of the MaxCliqueDyn algorithm from the 2000s. Its application can be widespread in computational chemistry, or communications.

Possibly related to algorithms for submodular functions as mentioned in an earlier answer could be those algorithms solving matroid partitioning. Many advances have been made since Edmonds or Cunningham(1980s). See more recent reference for more about matroid partitioning. With Oracle techniques, or efficient use of binary search new algorithmic techniques could be introduced. Although the treatment may be considered mathematical.

Answer 10

I would suggest maximal entropy random walk - there are lots of algorithms based on random walk, and the naive choice (uniform probability among outgoing edges) often turns out suboptimal.