1
$\begingroup$

I am wondering if there are some particularly rich problems that have a large intersection with algorithms and data structures. An example could be the travelling salesman problem. Any other suggestions ?

$\endgroup$

1 Answer 1

4
$\begingroup$

I suggest the longest increasing subsequence problem: Given an input sequence of length $n$, find the length of the longest increasing subsequence in the input sequence.

A naive dynamic programming-based formulation will lead to an $O(n^2)$ running time. The Wikipedia link provided above uses a binary search-based formulation to speed it up to $O(n \log n)$-time. Fredman '75 suggested in his paper another approach based on dynamic programming that obtains the same $O(n \log n)$ time bound, and established a lower bound in terms of the number of comparisons, proving his algorithm is the best possible.

But this is not the end of story, yet. There are various other algorithms that solve LIS. Using advanced data structures, Crochemore and Porat gives a priority queue-based algorithm for solving LIS in $O(n \log \log k)$-time on a word RAM. Yet other techniques exist, such as reduction to range maximum queries and then solving the problem via tournament trees 1, and using van Emde Boas trees. Finally, there is also a divide and conquer-based algorithm that solves LIS by Alam and Rahman, running in the same $O(n \log n)$ time bound.

The LIS problem also has connections in mathematics, it is related to a combinatorial structure called the Young tableaux (https://en.wikipedia.org/wiki/Young_tableau; in particular; the maintenance of the principle row of the Young tableaux is essentially solving for longest increasing subsequence) and the Robertson-Schensted correspondence.

Plenty of other problems in string pattern matching also have produced a rich body of results; I'm sure you'll find an abundance of other problems that are close in richness to longest increasing subsequence.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.