Lesson plan

Longest alternating subsequence

In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible. Formally, if \mathbf{x} = \{x_1, x_2, \ldots, x_n\} is a sequence of distinct real numbers, then the subsequence \{x_{i_1}, x_{i_2}, \ldots, x_{i_k}\} is alternating (or zigzag or down-up) if : x_{i_1} > x_{i_2} \cdots x_{i_k}\qquad \text{and} \qquad 1\leq i_1 Similarly, \mathbf{x} is reverse alternating (or up-down) if : x_{i_1} x_{i_3} Note that every sequence of length 1 is both alternating and reverse alternating. Let {\rm as}_n(\mathbf{x}) denote the length (number of terms) of the longest alternating subsequence of \mathbf{x} . For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that * {\rm as}_5(5,4,3,2,1) = 2 , because there are alternating subsequences of length 2, (for example 5,4 or 5,2 or 3,1), but all subsequences of length 3 are not alternating; * {\rm as}_5(1,2,3,4,5) = 1 , because all subsequences of length 2 are not alternating.…

Back to article

Article summary

In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible. Formally, if \mathbf{x} = \{x_1, x_2, \ldots, x_n\} is a sequence of distinct real numbers, then the subsequence \{x_{i_1}, x_{i_2}, \ldots, x_{i_k}\} is alternating (or zigzag or down-up) if : x_{i_1} > x_{i_2} \cdots x_{i_k}\qquad \text{and} \qquad 1\leq i_1 Similarly, \mathbf{x} is reverse alternating (or up-down) if : x_{i_1} x_{i_3} Note that every sequence of length 1 is both alternating and reverse alternating. Let {\rm as}_n(\mathbf{x}) denote the length (number of terms) of the longest alternating subsequence of \mathbf{x} . For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that * {\rm as}_5(5,4,3,2,1) = 2 , because there are alternating subsequences of length 2, (for example 5,4 or 5,2 or 3,1), but all subsequences of length 3 are not alternating; * {\rm as}_5(1,2,3,4,5) = 1 , because all subsequences of length 2 are not alternating.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.