<p>More attention has been given recently to sketching and streaming data structures, such as Bloom Filters, Count Min Sketch, HyperLogLog.</p>
<p>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.</p>

CC BY-SA 4.0
2023-08-07T14:23:36.263Z
Bloom filters date from 1970 so they don't qualify.
Michael Kay
CC BY-SA 4.0
2023-08-07T14:26:12.863Z
(I was going to suggest finger trees, but apparently they go back to 1977.)
Michael Kay
CC BY-SA 4.0
2023-08-07T19:00:52.640Z
Yeah, I should have clarified that the idea original is from 1970, but there was much more attention, development, generalization, and application since 2000. And if you are teaching these other new randomized data structures, you would teach Bloom filters too.
usul
CC BY-SA 4.0
2023-08-08T04:08:31.237Z
More modern replacements to Bloom filters (cuckoo filters, XOR filters) might fit the bill here as “modern.”
templatetypedef
CC BY-SA 4.0
2023-08-06T11:08:40.907Z
2023-08-06T11:08:40.907Z
usul
<p>Suffix arrays, with linear time construction. There are various algorithms, they're relatively approachable, and applications are plenty. SA-IS dates to 2009.</p>
<p>Soft heaps, they're not that complex, and have some neat applications. Dates to 2000, some newer tricks are more recent.</p>
<p>For off-line lowest-common-ancestor, Tarjans union-find based algorithm gets all the attention. It's not bad, but Schieber&amp;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.</p>
<p>Asymmetric numeral systems have largely replaced Huffman as the &quot;default entropy coding algorithm&quot; in the past decade or so. IDK if that deserves to be in <em>introduction to algorithms</em>, but Huffman coding sometimes shows up too</p>

CC BY-SA 4.0
2023-08-07T12:33:10.827Z
2023-08-07T12:33:10.827Z
user555045
<p>You could look at the <a href="https://en.wikipedia.org/wiki/Multiplicative_weight_update_method" rel="noreferrer">multiplicative weights update method</a>. 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.</p>

CC BY-SA 4.0
2023-08-05T23:43:23.393Z
2023-08-05T23:43:23.393Z
Peter Shor 
<p>Quantum algorithms would fit this, if one has time to introduce the model -- specifically, <a href="https://en.wikipedia.org/wiki/Grover%27s_algorithm" rel="noreferrer">Grover search</a> and possibly <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="noreferrer">Shor's algorithm</a>.</p>

CC BY-SA 4.0
2023-08-06T10:57:19.907Z
2023-08-06T10:57:19.907Z
usul
<p>I think we could include submodular optimization. Many common optimization problems can be framed as maximizing or minimizing <a href="https://en.wikipedia.org/wiki/Submodular_set_function" rel="noreferrer">submodular functions</a> 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.</p>

CC BY-SA 4.0
2023-08-06T10:51:51.647Z
2023-08-06T10:51:51.647Z
usul
<p>Perhaps <a href="https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo" rel="noreferrer">Markov Chain Monte Carlo</a>. 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.</p>

CC BY-SA 4.0
2023-08-06T11:21:01.680Z
2023-08-06T11:21:01.680Z
usul
<p>I guess it depends on what constitutes &quot;too advanced from a math point of view.&quot; It is natural that modern algorithmic ideas will involve more modern mathematics.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-08-05T21:17:12.503Z
2023-08-05T21:17:12.503Z
NaturalLogZ
<p>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.
<a href="https://www.jstor.org/stable/2007888" rel="nofollow noreferrer">https://www.jstor.org/stable/2007888</a></p>

CC BY-SA 4.0
2023-08-07T14:09:04.957Z
2023-08-07T14:09:04.957Z
Raphael Treccani-Chinelli
<p>I would suggest <a href="https://en.wikipedia.org/wiki/Maximal_entropy_random_walk" rel="nofollow noreferrer">maximal entropy random walk</a> - there are lots of algorithms based on random walk, and the naive choice (uniform probability among outgoing edges) often turns out suboptimal.</p>

CC BY-SA 4.0
2023-08-12T15:56:58.343Z
2023-08-12T15:56:58.343Z
Jarek Duda
<p>Some search based algorithms such for finding(or enumerating) Maximal Cliques have been around for a while, eg <a href="https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm" rel="nofollow noreferrer">Bron-Kerbosch</a> from the 70s. Related to such maximal clique finding algorithms could be that of the <a href="https://en.wikipedia.org/wiki/MaxCliqueDyn_maximum_clique_algorithm" rel="nofollow noreferrer">MaxCliqueDyn</a> algorithm from the 2000s. Its application can be widespread in computational chemistry, or communications.</p>
<p>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 <a href="https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p67_A1b.pdf" rel="nofollow noreferrer"> Edmonds </a> or <a href="https://epubs.siam.org/doi/10.1137/0215066" rel="nofollow noreferrer">Cunningham(1980s)</a>. See more recent <a href="https://arxiv.org/pdf/2303.05920.pdf" rel="nofollow noreferrer">reference</a> 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.</p>

CC BY-SA 4.0
2023-08-09T22:47:48.750Z
2023-08-09T22:47:48.750Z
user3483902
<p>Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, <a href="https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm" rel="nofollow noreferrer">Ford–Fulkerson algorithm</a> 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.</p>
<p><strong>Question:</strong> 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 <em>Introduction to algorithms</em> course?</p>
<p>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).</p>
<p>Or, did our academical ancestors in the 1950s already discover all the 'classics'?</p>

CC BY-SA 4.0
2023-08-05T23:02:40.940Z
Graph isomorphism was not shown to be not NP-complete. It was shown to be in QP. And no one knows if QP=NP or not (or even NP=P).
Lamine
CC BY-SA 4.0
2023-08-06T10:32:35.820Z
@Lamine ok fair point
Per Alexandersson
CC BY-SA 4.0
2023-08-08T14:48:39.467Z
@Lamine: Graph isomorphism was not shown to be in QP (unless I've missed something) but in pseudopolynomial time, which means that under the (weak) exponential time hypothesis, it's not NP-complete.
Peter Shor 
CC BY-SA 4.0
2023-08-08T17:04:16.037Z
@PeterShor You're right. I had a wrong definition of QP.
Lamine
CC BY-SA 4.0
2023-08-10T12:35:53.570Z
@PeterShor According to the Complexity Zoo, QP means quasipolynomial time, and the title of Babai's paper is "Graph isomorphism in quasipolynomial time".
Laakeri
<ds.algorithms><reference-request><ds.data-structures><big-list>
What are examples of recent relatively simple 'toolbox algorithms'?
Per Alexandersson
# What are examples of recent relatively simple 'toolbox algorithms'?

(Asked by: username_0 on 2023-08-05)

Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, [Ford–Fulkerson algorithm](https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_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'?

**Tags:** ds.algorithms, reference-request, ds.data-structures, big-list

> **Comments:**
> **username_1**: Graph isomorphism was not shown to be not NP-complete. It was shown to be in QP. And no one knows if QP=NP or not (or even NP=P).  
> **username_0**: @username_1 ok fair point  
> **username_2**: @username_1: Graph isomorphism was not shown to be in QP (unless I've missed something) but in pseudopolynomial time, which means that under the (weak) exponential time hypothesis, it's not NP-complete.  
> **username_1**: @PeterShor You're right. I had a wrong definition of QP.  
> **username_3**: @PeterShor According to the Complexity Zoo, QP means quasipolynomial time, and the title of Babai's paper is "Graph isomorphism in quasipolynomial time".  

---

## 10 answers

### Answer by username_4 on 2023-08-06. Score: 11

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.

> **Comments:**
> **username_5**: Bloom filters date from 1970 so they don't qualify.  
> **username_5**: (I was going to suggest finger trees, but apparently they go back to 1977.)  
> **username_4**: Yeah, I should have clarified that the idea original is from 1970, but there was much more attention, development, generalization, and application since 2000. And if you are teaching these other new randomized data structures, you would teach Bloom filters too.  
> **username_6**: More modern replacements to Bloom filters (cuckoo filters, XOR filters) might fit the bill here as “modern.”  

---

### Answer by username_7 on 2023-08-07. Score: 11

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 by username_4 on 2023-08-06. Score: 10

Quantum algorithms would fit this, if one has time to introduce the model -- specifically, [Grover search](https://en.wikipedia.org/wiki/Grover%27s_algorithm) and possibly [Shor's algorithm](https://en.wikipedia.org/wiki/Shor%27s_algorithm).


---

### Answer by username_2 on 2023-08-05. Score: 8

You could look at the [multiplicative weights update method](https://en.wikipedia.org/wiki/Multiplicative_weight_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 by username_4 on 2023-08-06. Score: 6

I think we could include submodular optimization. Many common optimization problems can be framed as maximizing or minimizing [submodular functions](https://en.wikipedia.org/wiki/Submodular_set_function) 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 by username_4 on 2023-08-06. Score: 6

Perhaps [Markov Chain Monte Carlo](https://en.wikipedia.org/wiki/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 by username_8 on 2023-08-05. Score: 5

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 by username_9 on 2023-08-07. Score: 4

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 by username_10 on 2023-08-12. Score: 0

I would suggest [maximal entropy random walk](https://en.wikipedia.org/wiki/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.


---

### Answer by username_11 on 2023-08-09. Score: 0

Some search based algorithms such for finding(or enumerating) Maximal Cliques have been around for a while, eg [Bron-Kerbosch](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm) from the 70s. Related to such maximal clique finding algorithms could be that of the [MaxCliqueDyn](https://en.wikipedia.org/wiki/MaxCliqueDyn_maximum_clique_algorithm) 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](https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p67_A1b.pdf)  or [Cunningham(1980s)](https://epubs.siam.org/doi/10.1137/0215066). See more recent [reference](https://arxiv.org/pdf/2303.05920.pdf) 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.


---

