京都大学 情報学研究科 知能情報学専攻 2019年2月実施 専門科目 F1-1

标签：

• Kyoto-University
• Dynamic-Programming

Author

itsuitsuki

Description (English)

Q.1

Given two sequences of length $n$, write pseudocode of an $O(n^2)$-time algorithm to find a longest common subsequence. Note that a subsequence does not necessarily have to be contiguous. For example, if $X = (A, B, C, B, D, A, B)$ and $Y = (B, D, C, A, B, A, B)$, the sequence $(B, C, A)$ is a common (but not longest) subsequence of $X$ and $Y$.

Q.2

Given a sequence of permuted integers from 1 to $n$, write pseudocode of an $O(n \log n)$-time algorithm to find the length of the longest monotonically increasing subsequence.

Kai