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.…
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
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- 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.